Difference between revisions of "TADM2E 2.8"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
(Undo revision 854 by Tada! (talk))
 
(2 intermediate revisions by 2 users not shown)
Line 96: Line 96:
 
Solution:  
 
Solution:  
  
<math>\lim_{n \to \infty} \frac{2^n}{10n^2} = \frac{1}{10} (\lim_{n \to \infty} \frac{2^n}{n^2}) = \frac{1}{10} (\lim_{n \to \infty} \frac{n * 2^{n-1}}{2 * n})</math> <span style='padding-left:10px'>(L'Hopital's Rule)</span>
+
<math>
 
+
\begin{align}
<math> = \frac{1}{10} (\lim_{n \to \infty} 2^{n-2}) = \infty </math>
+
&\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>f(n)=2^n</math>; <math>g(n)=3^n</math>==
 
==<math>f(n)=2^n</math>; <math>g(n)=3^n</math>==

Latest revision as of 15:54, 23 July 2020

2-8.

For each of the following pairs of functions, either $ f(n) $ is in $ O(g(n)) $, $ f(n) $ is in $ \Omega(g(n)) $, or $ f(n)=\Theta(g(n)) $. Determine which relationship is correct and briefly explain why.


$ f(n)=\log n^2 $; $ g(n)=\log n $ + $ 5 $

Answer: $ \log n^2 = \Theta (\log n + 5) $


Solution:

$ \log n^2 = 2 \times \log n $

$ 2 \times \log n \le 2 \times \log n + 10 $

$ \log n^2 \le 2 (\log n + 5) $

$ \log n^2 \le C (\log n + 5) $ (where $ C=2 $)

$ \log n^2 = O (\log n + 5) $

Also:

$ \log n + 5 \le \log n + 5 \log n $

$ \log n + 5 \le 6 \log n $

$ \log n + 5 \le 3 \times 2 \log n $

$ 3 \times \log n^2 \ge \log n + 5 $

$ \log n^2 \ge C \times (\log n + 5) $ (Where $ C =\frac{1}{3} $)

$ log n^2 = \Omega (\log n + 5) $

And therefore:

$ log n^2 = \Theta (\log n + 5) $


$ f(n)=\sqrt{n} $; $ g(n)=\log(n^2) $

Answer: $ f(n) = \Omega(g(n)) $


Solution:

$ g(n) = \log (n^2) = 2 * \log (n) $

$ \lim_{n \to \infty} \frac{\sqrt{n}}{2 * log(n)} = 2 * \lim_{n \to \infty} \frac{\sqrt{n}}{log(n)} = \infty $


$ f(n)=\log^2(n) $; $ g(n)=\log (n) $

Answer: $ f(n) = \Omega(g(n)) $


Solution:

$ \lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty $


$ f(n)=n $; $ g(n)=\log^2(n) $

Answer: $ f(n) = \Omega(g(n)) $


Solution:

$ \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 $


$ f(n)=n * \log(n) + n $; $ g(n)=\log (n) $

Answer: $ f(n) = \Omega(g(n)) $


Solution:

$ \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 $


$ f(n)=10 $; $ g(n)=\log (10) $

Answer: $ f(n) = \Theta(g(n)) $


Solution: Both are constants. Constants are always within a constant factor, $ c $, of each other (as $ n \rightarrow \infty $).


$ f(n)=2^n $; $ g(n)=10n^2 $

Answer: $ f(n) = \Omega(g(n)) $


Solution:

$ \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} $

$ f(n)=2^n $; $ g(n)=3^n $

Answer: $ f(n) = O(g(n)) $


Solution:

$ \lim_{n \to \infty} \frac{2^n}{3^n} = \lim_{n \to \infty} (\frac{2}{3})^n = 0 $