Consider the functions $f(n) = n^2$ and g(n) = $2^{log_2$ n}. What is the relation between f(n) and g(n)?
g(n) = $2^{log_2$ n} = n. Since $f(n) = n^2$, g(n) = $n = o(n^2) = o(f(n))$.
Which of the following functions grows asymptotically fastest as n -> infinity?
Order of growth: $n^{log$ n} < $2^n$ < (log n)^n < n! (for sufficiently large n). n! is the fastest growing function among the choices.
Let $f(n) = n^0$.99 log n and g(n) = n. Which of the following is TRUE?
lim ($n^0$.99 log n / n) = lim (log n / $n^0$.01) = 0 by L'Hopital's rule. Hence f(n) = o(g(n)).
What is the asymptotic growth rate of f(n) = 2^{$2^n}$ compared to g(n) = (n!)!?
(n!)! grows much faster than 2^{$2^n}$. Taking double log: log log f(n) = n, whereas log log g(n) $\approx n log n$. Thus f(n) = o(g(n)).
Arranging the functions f1(n) = $n^100$, f2(n) = $2^n$, f3(n) = $2^(sqrt(2$ log n)), f4(n) = n! in increasing order of asymptotic growth yields:
f3(n) = $2^(sqrt(2$ log n)) grows slower than any polynomial $n^k$ (so f3 < f1). f1(n) = $n^100$ < $2^n$ < n!. Order: f3, f1, f2, f4.