Prove that the function fn 2n3 2n73 log2 n 5 is On3 Prov

Prove that the function f(n) = 2n^3 + 2n^7/3 + log_2 n + 5 is O(n^3). Prove that the function f(n) = (log_2 n)^2 is O(n). Prove that the function f(n) = 2^n + 3 is Theta (2^n).

Solution

Ans. b) The maximum power in the entire expression is 3. All others are smaller than 3. Therefore, the maximum bound will be controlled by (n ^ 3). Hence, it is O(n^3).

Ans. c) Put log n as k. Therefore, it will become k^2 which will further be less than n since we have base 2 in k.
   Hence, it is O(n).

Ans. d) 2^(n+3) = 2^(n).2^(3) which is always greater than 2^n. Hence, it is Theta (2^n).