If f(n) = O(g(n)), then $2^(f(n))$ = O($2^(g(n)))$ is:
Counterexample: Let f(n) = 2n and g(n) = n. f(n) = O(g(n)) holds. But $2^(f(n))$ = $2^{2n}$ = $4^n$, and $2^(g(n))$ = $2^n$. $4^n$ is NOT O($2^n)$.
Which of the following statements is FALSE for asymptotic notations?
Big-O allows f(n) = g(n) (e.g., f(n)=n, g(n)=n => $f=O(g)), whereas small-o requires strict inequality (lim f/g = 0$). Thus $f=O(g) does NOT imply f=o(g)$.
What is the asymptotic tight bound for f(n) = $\sum_{$$i=1}^{n} i^k$ for a fixed constant integer k >= 1?
By integral approximation, $\sum_{$$i=1}^{n} i^k \approx \int_{0}^{n} x^k dx = n^{k+1} / (k+1) = \Theta(n^{k+1})$.
Consider the recurrence relation T(n) = T(n - 1) + 1/n with T(1) = 1. What is the asymptotic tight bound for T(n)?
T(n) = 1 + 1/2 + 1/3 + ... + 1/$n = H_{n} (Harmonic number)$, which is asymptotically $\Theta(log n)$.
What is the asymptotic complexity of the sum S(n) = 1 + 1/2 + 1/4 + 1/8 + ... + 1/($2^k)$ where $2^k$ <= n?
This is a converging geometric series with first term 1 and common ratio 1/2. The infinite sum equals 1/(1 - 1/2) = 2. Thus S(n) = $\Theta(1)$.