L2 (Asymptotic Notation)

Question 1

What does it mean to say f(n) is in O(g(n)), or f(n) = O(g(n))?

What does this mean in terms of the runtime of the algorithm?

Answer 1

• We say f(n) = O(g(n)) if there exists constants N > 0 and c > 0 such that f(n) <= c*g(n) for all n >= N
• This means that the run-time of the algorithm has an upper bound of O(g(n))

Question 2

We use the terms f(n) and g(n) when describing big-O notation. What exactly are these functions?

Answer 2

f(n) and g(n) are functions which map positive integers (n) to positive real numbers

Question 3

What does it mean to say f(n) is in Omega(g(n)), or f(n) = Omega(g(n))?

What does this mean in terms of the runtime of the algorithm?

Answer 3

• We say f(n) = Omega(g(n)) if there exists constants N > 0 and c > 0 such that f(n) >= c*g(n) for all n >= N
• This means that the runtime of the algorithm has a lower bound of Omega(g(n))

Question 4

f = ____ tells us that f grows no faster than g
f = ____ tells us that f grows at least as fast as g
f = ____ tells us that f and g grow at the same rate

Answer 4

O(g)
Omega(g)
Theta(g)

Question 5

What does it mean to say f(n) is in Theta(g(n)), or f(n) = Theta(g(n))?

What does this mean in terms of the runtime of the algorithm?

Answer 5

• We say f(n) = Theta(g(n)) if there exists constants c1 > 0, c2 > 0 and N > 0 such that c1g(n) >= f(n) >= c2g(n) for all n >= N
• This means that f(n) is in both O(g(n)) and Omega(g(n))
• The runtime has both an upper and lower bound of g(n)