Mini #1, 15451 Spring 2009
                 ========================

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

Problem 1:
Let N > 1 be an integer.
a) How long is the binary representation of N in big-O notation?
b) What is the running time of the following primality testing algorithm?
isprime(N):
        for i = 2 to floor(sqrt(N)):
                if N mod i == 0:
                        return false    # i is a factor of N
        return true
Assume that floor, sqrt and mod each take constant time.
c) Is this a polynomial time algorithm? Please explain.

Problem 2:
a) Can there be three functions f(n), g(n) and h(n) such that f(n) = o(g(n)),
g(n) = o(h(n)) and f(n) = Theta(h(n)). If yes, give an example. If no, explain
why? See Definition 2.3 in the lecture notes for Theta.

b) For any two functions f(n) and h(n), must it be the case that
f(n) = O(h(n)) OR f(n) = Omega(h(n)). Explain why or give a counterexample
showing why not. See Definition 2.2 in the lecture notes for Omega.

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)).

(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+epsilon}, g(n) = n*lg(n).  ["^" is "to the power", epsilon>0]
(c) f(n) = 2^n, g(n) = 3^n.
(d) log(log(n)), (log(n))^(1/2).