Mini #1, 15451 Fall 2009
========================
This mini is due via *email* to your TA, by 11:59pm Tuesday Sept 1.
Please use the subject line "15-451 MINI #1" in your email.
Problem 1: Suppose we have three functions f(n), g(n), and h(n) such
that f(n) = Omega(g(n)) and g(n) = Omega(h(n)). Must it be the case
that f(n) = Omega(h(n))? Explain why or give a counterexample showing
why not.
Problem 2: Suppose instead we have f(n) = O(g(n)) and g(n) = Omega(h(n)).
(a) Must it be the case that f(n) = O(h(n))? Explain why or give a
counterexample showing why not.
(b) Must it be the case that f(n) = Omega(h(n))? Explain why or give a
counterexample showing why not.
Problem 3: For each pair of functions below, list which of the
following are true: f(n) = o(g(n)), f(n) = Theta(g(n)), or g(n) =
o(f(n)).
(a) f(n) = ln(n), g(n) = lg(n). ["ln" is log-base-e, and "lg" is log-base-2]
(b) f(n) = n^{1.5}, g(n) = n * (lg n)^2. ["^" is "to the power"]
(c) f(n) = 2^n, g(n) = n^10.