Mini #1, 15451 Fall 2010
                 ========================

This mini is due via *email* to your TA, by 11:59pm Tuesday, August 31.
Please use the subject line "15-451 MINI #1" in your email.  Make sure to 
include your andrew id in the email.


Problem 1: Suppose that we have 3 functions: f(n), g(n) and h(n) such 
that f(n) = O(g(n)) and f(n) = O(h(n)). Does it follow that 
g(n) = O(h(n))? Explain why or give a counterexample showing why not.

Problem 2: Given three functions f(n), g(n) and h(n) such that
f(n) = Theta(g(n)) and g(n) = O(h(n)),

   (a) Is h(n) = Omega(f(n))? Provide a brief (one/two sentence) 
       justification of your answer.

   (b) Given another function k(n) such that h(n) = Omega(k(n)), show that it is 
       not possible to relate k(n) and f(n) using one of the above asymptotic 
       notations (O, Omega, o, Theta) by providing two specific examples of 
       functions f,h,and k such that f(n) = o(k(n)) in the first example and 
       k(n) = o(f(n)) in the second example (remember that both examples must 
       satisfy h(n) = Omega(k(n)) and h(n) = Omega(f(n))).

         Example 1: f(n) = ___, h(n) = ___, k(n) = ___
         Example 2: f(n) = ___, h(n) = ___, k(n) = ___

Problem 3:
For each pair <f,g> of functions below, list ALL applicable 
from the following: 
f(n) = o(g(n)), g(n) = o(f(n)), f(n) = Theta(g(n)), f(n) = O(g(n)), g(n) = O(f(n)). 

"ln" is log-base-e, and "lg" is log-base-2. "^" is "to the power"

(a) f(n)=(lg(n))^(3/2)        g(n)=lg(n^(3/2))

(b) f(n)=ln(n)                g(n)=lg(n)

(c) f(n)=n^2              	  g(n)=2^((1/2)lg(n))