2.27

Answers

1. Choose [math]f(n)=n[/math], [math]g(n)=n^{2}[/math]. Then [math]\displaystyle\lim_{n\to\infty}\frac{f(n)}{g(n)}=\lim_{n\to\infty}\frac{n}{n^{2}}=0[/math], so [math]f(n)=o(g(n))[/math], and clearly the ratio does not stay between two positive constants, so [math]f(n)\neq\Theta(g(n))[/math].

2. None. If [math]f(n)=\Theta(g(n))[/math] it is already bounded below by a positive multiple of [math]g(n)[/math]; that precludes the stricter condition [math]f(n)=o(g(n))[/math] (except for the trivial zero function, which is not allowed because no positive constant lower bound can be found).

3. None. By definition, [math]f(n)=\Theta(g(n))[/math] implies both [math]f(n)=O(g(n))[/math] and [math]f(n)=\Omega(g(n))[/math]. Thus it is impossible for [math]f(n)\neq O(g(n))[/math].

4. Choose [math]f(n)=n^{2}[/math], [math]g(n)=n[/math]. There exists a constant [math]c>0[/math] (e.g. [math]c=1[/math]) such that [math]f(n)\ge c\,g(n)[/math] for all sufficiently large [math]n[/math], so [math]f(n)=\Omega(g(n))[/math]; however, [math]\frac{f(n)}{g(n)}=n\to\infty[/math], so no constant upper bound exists and [math]f(n)\neq O(g(n))[/math].

Back to Chapter 2