2.11

1. [math]f(n)=3n^{2},\;g(n)=n^{2}[/math]:  [math]f(n)=\Theta(g(n))[/math] (and thus also [math]O(g(n))[/math] and [math]\Omega(g(n))[/math]) because [math]f/g=3[/math].
2. [math]f(n)=2n^{4}-3n^{2}+7,\;g(n)=n^{5}[/math]:  [math]f(n)=O(g(n))[/math] only, since [math]f/g=2/n\to0[/math]; it is neither [math]\Theta(g(n))[/math] nor [math]\Omega(g(n))[/math].
3. [math]f(n)=\log n,\;g(n)=\log n+\dfrac1n[/math]:  [math]f(n)=\Theta(g(n))[/math] (hence [math]O[/math] and [math]\Omega[/math]) because [math]\displaystyle\lim_{n\to\infty}\frac{f}{g}=1[/math].
4. [math]f(n)=2^{k\log n},\;g(n)=n^{k}[/math]:  Since [math]2^{\log n}=n[/math], we have [math]f=g[/math]; therefore [math]f(n)=\Theta(g(n))[/math] (also [math]O[/math], [math]\Omega[/math]).
5. [math]f(n)=2^{\,n},\;g(n)=2^{\,2n}=4^{\,n}[/math]:  [math]f(n)=O(g(n))[/math] only, because [math]f/g=(1/2)^{n}\to0[/math]; it is not [math]\Theta(g(n))[/math] nor [math]\Omega(g(n))[/math].

Back to Chapter 2