Difference between revisions of "TADM2E 2.9"
(Blanked the page) |
|||
| Line 1: | Line 1: | ||
| + | =2-9.= | ||
| + | For each of the following pairs of functions <math>f(n)</math> and <math>g(n)</math>, determine whether <math>f(n) = O(g(n))</math>, <math>g(n) = O(f(n))</math>, or both. | ||
| + | |||
| + | =='''1.''' <math>f(n) = \frac{n^2 - n}{2}</math>; <math>g(n) = 6 n</math>== | ||
| + | |||
| + | Answer: <math>g(n) = O(f(n)) </math> | ||
| + | |||
| + | |||
| + | Solution: Constant factors can be ignored; we only need to pay attention to the 'largest' term. <math>n^2</math> outgrows <math>n</math> as <math>n \rightarrow \infty</math>. Therefore, <math>f(n)</math> outgrows <math>g(n)</math>. | ||
| + | |||
| + | |||
| + | =='''2.''' <math>f(n) = n + 2\sqrt{n}</math>; <math>g(n) = n^2</math>== | ||
| + | |||
| + | Answer: <math>f(n) = O(g(n))</math> | ||
| + | |||
| + | |||
| + | Solution: <math>n^2</math> outgrows n. We ignore <math>2\sqrt{n}</math> since <math>n</math> outgrows <math>\sqrt{n}</math>. | ||
| + | |||
| + | |||
| + | =='''3.''' <math>f(n) = n * log (n) </math>; <math>g(n) = \frac{n \sqrt{n}}{2}</math>== | ||
| + | |||
| + | Answer: <math>f(n) = O(g(n))</math> | ||
| + | |||
| + | |||
| + | Solution: Both sides have a factor of <math>n</math>, so we ignore it. <math>\sqrt{n}</math> outgrows <math>log(n)</math>, so <math>g(n)</math> is bigger. | ||
| + | |||
| + | |||
| + | =='''4.''' <math>f(n) = n + log(n)</math>; <math>g(n) = \sqrt{n}</math>== | ||
| + | |||
| + | Answer: <math>g(n) = O(f(n))</math> | ||
| + | |||
| + | |||
| + | Solution: <math>n</math> outgrows <math>\sqrt{n}</math>. | ||
| + | |||
| + | |||
| + | =='''5.''' <math>f(n) = 2 * log^2(n)</math>; <math>g(n) = log(n) + 1</math>== | ||
| + | |||
| + | Answer: <math>g(n) = O(f(n))</math> | ||
| + | |||
| + | |||
| + | Solution: <math>log^2(n)</math> grows faster than <math>log(n)</math>. | ||
| + | |||
| + | <math>\lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty</math> | ||
| + | |||
| + | |||
| + | =='''6.''' <math>f(n) = 4n * log(n) + n</math>; <math>g(n) = \frac{n^2 - n}{2}</math>== | ||
| + | |||
| + | Answer: <math>f(n) = O(g(n))</math> | ||
| + | |||
| + | |||
| + | Solution: <math>n^2</math> outgrows <math>n * log(n)</math>. | ||
Revision as of 01:00, 1 August 2020
Contents
- 1 2-9.
- 1.1 1. $ f(n) = \frac{n^2 - n}{2} $; $ g(n) = 6 n $
- 1.2 2. $ f(n) = n + 2\sqrt{n} $; $ g(n) = n^2 $
- 1.3 3. $ f(n) = n * log (n) $; $ g(n) = \frac{n \sqrt{n}}{2} $
- 1.4 4. $ f(n) = n + log(n) $; $ g(n) = \sqrt{n} $
- 1.5 5. $ f(n) = 2 * log^2(n) $; $ g(n) = log(n) + 1 $
- 1.6 6. $ f(n) = 4n * log(n) + n $; $ g(n) = \frac{n^2 - n}{2} $
2-9.
For each of the following pairs of functions $ f(n) $ and $ g(n) $, determine whether $ f(n) = O(g(n)) $, $ g(n) = O(f(n)) $, or both.
1. $ f(n) = \frac{n^2 - n}{2} $; $ g(n) = 6 n $
Answer: $ g(n) = O(f(n)) $
Solution: Constant factors can be ignored; we only need to pay attention to the 'largest' term. $ n^2 $ outgrows $ n $ as $ n \rightarrow \infty $. Therefore, $ f(n) $ outgrows $ g(n) $.
2. $ f(n) = n + 2\sqrt{n} $; $ g(n) = n^2 $
Answer: $ f(n) = O(g(n)) $
Solution: $ n^2 $ outgrows n. We ignore $ 2\sqrt{n} $ since $ n $ outgrows $ \sqrt{n} $.
3. $ f(n) = n * log (n) $; $ g(n) = \frac{n \sqrt{n}}{2} $
Answer: $ f(n) = O(g(n)) $
Solution: Both sides have a factor of $ n $, so we ignore it. $ \sqrt{n} $ outgrows $ log(n) $, so $ g(n) $ is bigger.
4. $ f(n) = n + log(n) $; $ g(n) = \sqrt{n} $
Answer: $ g(n) = O(f(n)) $
Solution: $ n $ outgrows $ \sqrt{n} $.
5. $ f(n) = 2 * log^2(n) $; $ g(n) = log(n) + 1 $
Answer: $ g(n) = O(f(n)) $
Solution: $ log^2(n) $ grows faster than $ log(n) $.
$ \lim_{n \to \infty} \frac{log^2(n)}{log(n)} = \lim_{n \to \infty} log(n) = \infty $
6. $ f(n) = 4n * log(n) + n $; $ g(n) = \frac{n^2 - n}{2} $
Answer: $ f(n) = O(g(n)) $
Solution: $ n^2 $ outgrows $ n * log(n) $.
