Mini #1, 15451 Fall 2011
                 ========================

This mini is due via *email* to your TA, by 11:59pm Tuesday Sept 6.
Please use the subject line "15-451 MINI #1" in your email.

Problem 0: Sign into the piazza discussion board system, using your
andrew ID (so your TA can check off that you did it).

Problem 1: Suppose f(n) = O(g(n)).  Does that imply that g(n) =
Omega(f(n))?  Explain why or give a counterexample.

Problem 2: For each pair <f,g> 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^5.

Problem 3: Give an example of two crazy functions f and g such that
f(n) != O(g(n)) and g(n) != O(f(n)).  [here, "!=" is "not equal"]
To make this more challenging, f and g must be functions from Z+ to Z+
(they are not allowed to be negative or zero).