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

(b₁) f(n) + c = O(f(n)).

(b₂) If f(n) 1, then f(n) + c = O(f(n)).

(c₁) If f(n) = O(g(n)), log(f(n)) 0 and log(g(n)) 0, then log(f(n)) = O(log(g(n))).

(c₂) If f(n) = O(g(n)), log(f(n)) 0 and log(g(n)) 1, then log(f(n)) = O(log(g(n))).

(d₁) f(2n) = (f(n)).

(d₂) If f(n) = O(n^c), then f(2n) = O(n^c).

(d₃) If f(n) = (n^c), 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).

na na

(logn)^a log(bn) aⁿ

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, 2ⁿ. Then, the asymptotical ordering is: log(.