Mini #1, 15-451 Spring 2007
===========================
This mini is to be completed individually and is due via *email* to your
TA by midnight Tuesday Jan 23rd.
Please use the subject line "15-451 MINI #1" in your email.
Problem 1: Given an integer N>1 in binary representation, algorithm A
returns whether N is prime or not
and runs in cubic time (in the length of the input). What is the running
time of A in terms of N?
(a) O(N^3) (b) O((lgN)^3) (c) O(lg(N^3))
Problem 2: Suppose we have three functions f(n), g(n), and h(n) such
that f(n) = Omega(h(n)) and g(n) = Omega(h(n)). Must it be the case that
f(n) = Theta(g(n))? Explain why or give a counterexample showing why not.
Problem 3: For each pair 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*(ln(n))^100.
(c) f(n) = 2^(lg(n)), g(n) = 2^(2lg(n)). ["^" is "to the power"]