Oh, Omega, Theta

Question 1

When describing the asymptotic efficiency, what are we actually talking about?

Answer 1

The “growth of functions”

Question 2

Why are we focusing on the asymptotic time?

Answer 2

To abstract away low-order terms and constant factors.

Question 3

What does Oh, Omega and Theta asymptotically correspond to?

Answer 3

• Oh - Less or equal
• Omega - More or equal
• Theta - Equal

Question 4

Give the bounding properties of Oh, Omega and Theta.

Answer 4

• Oh - asymptotic upper bound
• Omega - asymptotic lower bound
• Theta - asymptotic tight bound

Question 5

What is the bounding property of Oh?

Answer 5

Upper bound

Question 6

What is the bounding property of Omega?

Answer 6

Lower bound

Question 7

What is the bounding property of Theta?

Answer 7

Tight bound

Question 8

With O(n^2), are these functions asymptotically upper bounded by n^2?

1. 2n^2
2. n^2 + n
3. n^2.00001
4. n^2 + 1000n
5. n
6. n^2 . lg(n)
7. n/1000
8. n^1.999999
9. n^2 / lg(n)

Answer 8

1. Yes
2. Yes
3. No
4. Yes
5. Yes
6. No
7. Yes
8. Yes
9. Yes

Question 9

With Omega(n^2), are these functions asymptotically lower-bounded by n^2?

1. n^1.99999
2. 1/2 n^2
3. n^2 / lg(n)
4. n^2 + n
   5 n^2 - n
5. n^3
6. 2^2^n
7. n^2 . lg(n)

Answer 9

1. No
2. Yes
3. No
4. Yes
5. Yes
6. Yes
7. Yes
8. Yes

Question 10

What is the overall worst-case of Insertion Sort?

Answer 10

O(n^2) (also, Theta(n^2))

Question 11

Roughly, what are the four categories growth rates typically fall into?

Answer 11

• Constant
• Logarithmic
• Polynomial
• Exponential