Which of the following formal statements correctly defines f(n) = O(g(n))?
By definition, f(n) = O(g(n)) if there exist positive constants c > 0 and n0 >= 1 such that 0 <= f(n) <= c * g(n) for all n >= n0.
If f(n) = O(g(n)) and g(n) = O(h(n)), which of the following properties guarantees that f(n) = O(h(n))?
Asymptotic upper bound O(.) satisfies the transitivity property: if f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)).
Which of the following is TRUE regarding small-o notation (f(n) = o(g(n)))?
Small-o notation denotes an asymptotically strict upper bound. Formally, f(n) = o(g(n)) if and only if $\lim_{n \to \infty} (f(n) / g(n)) = 0$.
Which of the following represents the correct relationship between $f(n) = 2^n$ and g(n) = $3^n$?
lim ($2^n / 3^n)$ = lim (2/3)^$n = 0$. Therefore, 2^$n = o(3^n)$.
What is the asymptotic relation between f(n) = $\log(n!)$ and g(n) = n log n?
By Stirling's approximation, $\log(n!) = n log n - n + O(log n)$. Thus $\log(n!) = \Theta(n log n)$.