Problem 1
For the following statements, consider the functions f(n), g(n) and constant c such that f(n) ≥ 0, g(n) ≥ 0, and c 0. Indicate whether the statements are true or false. If true prove the statement by providing a formal argument based on the definition of asymptotic notation, otherwise, provide a counter-example to prove that they are false.
(a) max{f(n),g(n)} = Θ(f(n) + g(n)).
(b1) f(n) + c = O(f(n)).
(b2) If f(n) ≥ 1, then f(n) + c = O(f(n)).
(c1) If f(n) = O(g(n)), log(f(n)) ≥ 0 and log(g(n)) ≥ 0, then log(f(n)) = O(log(g(n))).
(c2) If f(n) = O(g(n)), log(f(n)) ≥ 0 and log(g(n)) ≥ 1, then log(f(n)) = O(log(g(n))).
(d1) f(2n) = Θ(f(n)).
(d2) If f(n) = O(nc), then f(2n) = O(nc).
(d3) If f(n) = Θ(nc), then f(2n) = Θ(f(n)).
Problem 2
Assume , a and b are constants such that 0 . Sort the following functions in asymptotically increasing order and indicate when two or more functions are asymptotically equivalent (see definition below). Briefly justify your answers (no formal proof is needed).
n
n
an
bn
alogan
log(na)
log(nb)
n/a
n
(n + a)b
na+b
(n + b)a
n−a na
(logn)a log(bn) an
Definition. Two functions f(n) and g(n) are asymptotically equivalent if and only if f(n) = Θ(g(n)).
Example. Suppose we are sorting the following functions: n, log(n), 2n, 2n. Then, the asymptotical ordering is: log( .
