|
|
| 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>.
| |
