Mini #1, 15451 Fall 2004
                 ========================

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


Problem 1: An algorithm to factor positive integers takes as input a
binary number N and outputs the prime factorization of N.  

Q: What is n, the size (length) of the input, as a function of N?
Your answer should be correct up to +/- 1.


Problem 2: Suppose we have three functions f(n), g(n), and h(n) such
that f(n) = O(h(n)) and g(n) = O(h(n)).  Must it be the case that f(n)
= O(g(n))?  Explain why or give a counterexample showing why not.


Problem 3: 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^2, g(n) = n*lg(n).

   (c) f(n) = 2^n,  g(n) = 4^n.