Practice with Order of Growth
For each pair of \(f(n) \) and \(g(n) \) below, determine which of the listed relations apply.
-
\(f(n) = log_{3} n \) and \(g(n) = log_{7} n \)
\(\lim_{n \rightarrow \infty} |\frac{f(n)}{g(n)}| = \lim_{n \rightarrow \infty} \frac{ln(n) / ln(3)}{ln(n) / ln(7)} = \frac{ln(7)}{ln(3)} \) -
\(f(n) = 0 \) and \(g(n) = 33 \)
\(\lim_{n \rightarrow \infty} |\frac{f(n)}{g(n)}| = \lim_{n \rightarrow \infty} \frac{0}{33} = 0 \) -
\(f(n) = 1 + cos(\frac{\pi n}{2}) \) and \(g(n) = 1 + sin(\frac{\pi n}{2}) \)
\(\frac{f(n)}{g(n)} = 0 \) for \(n \equiv 1 (\text{mod } 4) \), and \(\frac{g(n)}{f(n)} = 0 \) for \(n \equiv 0 (\text{mod } 4) \), so the 2 functions and their quotient never converge to some limit. -
\(f(n) = 1.01^{n} \) and \(g(n) = n^{100} \)
\(\lim_{n \rightarrow \infty} |\frac{f(n)}{g(n)}| = \lim_{n \rightarrow \infty} \frac{1.01^{n}}{n^{100}} = \lim_{n \rightarrow \infty} \frac{1.01^{n} ln(1.01)}{100 \cdot n^{99}} = ... = \lim_{n \rightarrow \infty} \frac{1.01^{n} ln(1.01)^{100}}{100!} = \infty \)