2.9

For each of the following pairs of functions, either [math]\displaystyle{ f(n) }[/math] is in [math]\displaystyle{ O(g(n)) }[/math], [math]\displaystyle{ f(n) }[/math] is in [math]\displaystyle{ \Omega(g(n)) }[/math], or [math]\displaystyle{ f(n)=\Theta(g(n)) }[/math]. Determine which relationship is correct and briefly explain why.

[math]\displaystyle{ f(n)=\log n^2 }[/math]; [math]\displaystyle{ g(n)=\log n }[/math] + [math]\displaystyle{ 5 }[/math]

Answer: [math]\displaystyle{ \log n^2 = \Theta (\log n + 5) }[/math]

Solution:

[math]\displaystyle{ \log n^2 = 2 \times \log n }[/math]

[math]\displaystyle{ 2 \times \log n \le 2 \times \log n + 10 }[/math]

[math]\displaystyle{ \log n^2 \le 2 (\log n + 5) }[/math]

[math]\displaystyle{ \log n^2 \le C (\log n + 5) }[/math] (where [math]\displaystyle{ C=2 }[/math])

[math]\displaystyle{ \log n^2 = O (\log n + 5) }[/math]

Also:

[math]\displaystyle{ \log n + 5 \le \log n + 5 \log n }[/math]

[math]\displaystyle{ \log n + 5 \le 6 \log n }[/math]

[math]\displaystyle{ \log n + 5 \le 3 \times 2 \log n }[/math]

[math]\displaystyle{ 3 \times \log n^2 \ge \log n + 5 }[/math]

[math]\displaystyle{ \log n^2 \ge C \times (\log n + 5) }[/math] (Where [math]\displaystyle{ C =\frac{1}{3} }[/math])

[math]\displaystyle{ log n^2 = \Omega (\log n + 5) }[/math]

And therefore:

[math]\displaystyle{ log n^2 = \Theta (\log n + 5) }[/math]

[math]\displaystyle{ f(n)=\sqrt{n} }[/math]; [math]\displaystyle{ g(n)=\log(n^2) }[/math]

Answer: [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math]

Solution:

[math]\displaystyle{ g(n) = \log (n^2) = 2 * \log (n) }[/math]

[math]\displaystyle{ \lim_{n \to \infty} \frac{\sqrt{n}}{2 * log(n)} = 2 * \lim_{n \to \infty} \frac{\sqrt{n}}{log(n)} = \infty }[/math]

[math]\displaystyle{ f(n)=\log^2(n) }[/math]; [math]\displaystyle{ g(n)=\log (n) }[/math]

Answer: [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math]

Solution:

[math]\displaystyle{ \lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty }[/math]

[math]\displaystyle{ f(n)=n }[/math]; [math]\displaystyle{ g(n)=\log^2(n) }[/math]

Answer: [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math]

Solution:

[math]\displaystyle{ \lim_{n \to \infty} \frac{n}{\log^2(n)} = \lim_{n \to \infty} ((\frac{\sqrt{n}}{\log(n)})^2) = (\lim_{n \to \infty} \frac{\sqrt{n}}{\log(n)})^2 = \infty }[/math]

[math]\displaystyle{ f(n)=n * \log(n) + n }[/math]; [math]\displaystyle{ g(n)=\log (n) }[/math]

Answer: [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math]

Solution:

[math]\displaystyle{ \lim_{n \to \infty} \frac{n * \log(n) + n}{log(n)} = \lim_{n \to \infty} (\frac{n * \log(n)}{log(n)} + \frac{n}{log(n)}) = \lim_{n \to \infty} (n + \frac{n}{log(n)}) = \infty }[/math]

[math]\displaystyle{ f(n)=10 }[/math]; [math]\displaystyle{ g(n)=\log (10) }[/math]

Answer: [math]\displaystyle{ f(n) = \Theta(g(n)) }[/math]

Solution: Both are constants. Constants are always within a constant factor, [math]\displaystyle{ c }[/math], of each other (as [math]\displaystyle{ n \rightarrow \infty }[/math]).

[math]\displaystyle{ f(n)=2^n }[/math]; [math]\displaystyle{ g(n)=10n^2 }[/math]

Answer: [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math]

Solution:

[math]\displaystyle{ \begin{align} &\lim_{n \to \infty} \frac{2^n}{10n^2} \\ &\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{2^n}{n^2}\right) \\ &\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{\ln(2)\cdot 2^n}{2 \cdot n}\right) \text{L'Hopital's Rule} \\ &\implies \frac{1}{10} \left(\lim_{n \to \infty} \frac{2\ln(2)\cdot 2^n}{2}\right) \text{L'Hopital's Rule} \\ &\implies \frac{\ln(2)}{10} \lim_{n \to \infty} 2^n \\ &\implies \frac{\ln(2)}{10} \lim_{n \to \infty} 2^n = \infty \end{align} }[/math]

[math]\displaystyle{ f(n)=2^n }[/math]; [math]\displaystyle{ g(n)=3^n }[/math]

Answer: [math]\displaystyle{ f(n) = O(g(n)) }[/math]

Solution:

[math]\displaystyle{ \lim_{n \to \infty} \frac{2^n}{3^n} = \lim_{n \to \infty} (\frac{2}{3})^n = 0 }[/math]

Back to Chapter 2