Given a collection of functions f(n), g(n), etc., state whether or not f = O(g), f = Omega(g), f = Theta(g), f = o(g), f = omega(g). Sort the collection by asymptotic growth rate from least growth rate to highest.
Example Problem
Part a.
Let $f(n) = 3n^3 + 25$ and $g(n) = 20n^2 + 1$.
Answer the following True/False:
$f = O(g)$
$f = \Omega(g)$
$f = \Theta(g)$
$f = o(g)$
$f = \omega(g)$
Part b.
Let:
$f(n) = 3n^3 + 25$
$g(n) = 20n^2 + 1$
$h(n) = 2^{0.3 n}$
$w(n) = (\log(n))^4$
Sort $f,g,h,w$ by asymptotic growth rate, from least growth rate to highest growth rate.
Sample Solution
Part a.
False
True
False
False
True
Part b.
$w, g, f, h$
Rubric
Rubric for both Parts.
All answers to both parts must be fully correct in order to pass the question.
4 (Pass, Near-Perfect): all answers correct.
3 (Pass, Proficient): not applicable for this problem.
2 (Fail, Progress): mostly correct answers for Part a and/or mostly correct list in Part b, but not all correct.
1 (Fail, Wrong Track): few correct on Part a and/or mostly incorrect list in Part b.