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