TADM2E 2.9

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