Mini #1, 15451 Fall 2003
                ========================

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

Problem 1: An algorithm to factor positive integers takes as input a
number N and outputs the prime factorization of N.  Q: What is n, the
size (length) of the input, as a function of N?

Problem 2: For a pair of functions f and g, is it possible to have
f(n) = o(g(n)) *and* f(n) = Theta(g(n))?  Why or why not?  [Note, this
is "little-oh" not "big-Oh"]. 

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) = 100n^2,   g(n) = n^3.

  (b) f(n) = (lg n)^(lg n),   g(n) = n^(lg lg n)

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