Question 5 : 12 points The idea of bounding limits is a good way to compare algorithms. We need a formal methodology to apply it consistently. We define three asymptotic notations used to classify algorithm runtime. Little O: T(n) = o(f(n)) If for all positive constant c > 0 there exists an n0 0 such that for all n n0 we have 0 T(n) cf(n). Theta: T(n) = (f(n)) if there exists positive constants c1 > 0, c2 > 0, n0 0 such that for all n n0 we have c1f(n) T(n) c2f(n) Little Omega: T(n) = (f(n)) if for all positive constant c > 0 there exists an n0 0 such that for all n n0 we have 0 cf(n) T(n). Match each of these definitions to a limit condition. (a) (2 points) limn f(n) g(n) = A. f(n) = o(g(n)) B. f(n) = (g(n)) C. f(n) = (g(n)) (b) (2 points) limn f(n) g(n) = Some Constant Number A. f(n) = o(g(n)) B. f(n) = (g(n)) C. f(n) = (g(n)) (c) (2 points) limn f(n) g(n) = 0 A. f(n) = o(g(n)) B. f(n) = (g(n)) C. f(n) = (g(n)) (d) (2 points) limn f(n) g(n) = A. g(n) = o(f(n)) B. g(n) = (f(n)) C. g(n) = (f(n)) (e) (2 points) limn f(n) g(n) = Some Constant Number A. g(n) = o(f(n)) B. g(n) = (f(n)) C. g(n) = (f(n)) (f) (2 points) limn f(n) g(n) = 0 A. g(n) = o(f(n)) B. g(n) = (f(n)) C. g(n) = (f(n))