Difference between revisions of "TADM2E 2.8"
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
=2-8.= | =2-8.= | ||
| − | For each of the following pairs of functions, either | + | For each of the following pairs of functions, either <math>f(n)</math> is in <math>O(g(n))</math>, <math>f(n)</math> is in <math>\Omega(g(n))</math>, or <math>f(n)=\Theta(g(n))</math>. Determine which relationship is correct and briefly explain why. |
| − | == | + | ==<math>f(n)=\log n^2</math>; <math>g(n)=\log n</math> + <math>5</math>== |
| − | Answer: | + | Answer: <math>\log n^2 = \Theta (\log n + 5)</math> |
Solution: | Solution: | ||
| − | + | <math>\log n^2 = 2 \times \log n</math> | |
| − | + | <math>2 \times \log n \le 2 \times \log n + 10</math> | |
| − | + | <math>\log n^2 \le 2 (\log n + 5)</math> | |
| − | + | <math>\log n^2 \le C (\log n + 5)</math> (where <math>C=2</math>) | |
| − | + | <math>\log n^2 = O (\log n + 5)</math> | |
Also: | Also: | ||
| − | + | <math>\log n + 5 \le \log n + 5 \log n</math> | |
| − | + | <math>\log n + 5 \le 6 \log n</math> | |
| − | + | <math>\log n + 5 \le 3 \times 2 \log n</math> | |
| − | + | <math>3 \times \log n^2 \ge \log n + 5 </math> | |
| − | + | <math>\log n^2 \ge C \times (\log n + 5)</math> (Where <math>C =\frac{1}{3}</math>) | |
| − | + | <math>log n^2 = \Omega (\log n + 5)</math> | |
And therefore: | And therefore: | ||
| − | + | <math>log n^2 = \Theta (\log n + 5)</math> | |
| − | == | + | ==<math>f(n)=\sqrt{n}</math>; <math>g(n)=\log(n^2)</math>== |
| − | Answer: | + | Answer: <math>f(n) = \Omega(g(n))</math> |
Solution: | Solution: | ||
| − | + | <math>g(n) = \log (n^2) = 2 * \log (n)</math> | |
| − | + | <math>\lim_{n \to \infty} \frac{\sqrt{n}}{2 * log(n)} = 2 * \lim_{n \to \infty} \frac{\sqrt{n}}{log(n)} = \infty</math> | |
| − | == | + | ==<math>f(n)=\log^2(n)</math>; <math>g(n)=\log (n)</math>== |
| − | Answer: | + | Answer: <math>f(n) = \Omega(g(n))</math> |
Solution: | Solution: | ||
| − | + | <math>\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty</math> | |
| − | == | + | ==<math>f(n)=n</math>; <math>g(n)=\log^2(n)</math>== |
| − | Answer: | + | Answer: <math>f(n) = \Omega(g(n))</math> |
Solution: | Solution: | ||
| − | + | <math>\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>f(n)=n * \log(n) + n</math>; <math>g(n)=\log (n)</math>== |
| − | Answer: | + | Answer: <math>f(n) = \Omega(g(n))</math> |
Solution: | Solution: | ||
| − | + | <math>\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>f(n)=10</math>; <math>g(n)=\log (10)</math>== |
| − | Answer: | + | Answer: <math>f(n) = \Theta(g(n))</math> |
| − | Solution: Both are constants. Constants are always within a constant factor, | + | Solution: Both are constants. Constants are always within a constant factor, <math>c</math>, of each other (as <math>n \rightarrow \infty</math>). |
| − | == | + | ==<math>f(n)=2^n</math>; <math>g(n)=10n^2</math>== |
| − | Answer: | + | Answer: <math>f(n) = \Omega(g(n))</math> |
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> = \frac{1}{10} (\lim_{n \to \infty} 2^{n-2}) = \infty </math> | |
| − | == | + | ==<math>f(n)=2^n</math>; <math>g(n)=3^n</math>== |
| − | Answer: | + | Answer: <math>f(n) = O(g(n))</math> |
Solution: | Solution: | ||
| − | + | <math>\lim_{n \to \infty} \frac{2^n}{3^n} = \lim_{n \to \infty} (\frac{2}{3})^n = 0</math> | |
Revision as of 18:23, 11 September 2014
Contents
- 1 2-8.
- 1.1 $ f(n)=\log n^2 $; $ g(n)=\log n $ + $ 5 $
- 1.2 $ f(n)=\sqrt{n} $; $ g(n)=\log(n^2) $
- 1.3 $ f(n)=\log^2(n) $; $ g(n)=\log (n) $
- 1.4 $ f(n)=n $; $ g(n)=\log^2(n) $
- 1.5 $ f(n)=n * \log(n) + n $; $ g(n)=\log (n) $
- 1.6 $ f(n)=10 $; $ g(n)=\log (10) $
- 1.7 $ f(n)=2^n $; $ g(n)=10n^2 $
- 1.8 $ f(n)=2^n $; $ g(n)=3^n $
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:
$ \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}) $ (L'Hopital's Rule)
$ = \frac{1}{10} (\lim_{n \to \infty} 2^{n-2}) = \infty $
$ 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 $
