Big O notation on polynomials

Question

I'm required to prove/disprove the following:

Given constant positive $k$ and constant positive $a_k$ and real constants $a_0, ..., a_{k-1}$

$$n^k = O(\sum_{i=0}^{k}a_i \cdot n^{i})$$

I know this is true but can't manage to come up with a formal solution.

Answer 1

Let's start with a formal definition of $O(f)$. We have that $f(n)$ is $O(g(n))$ as $n \to \infty$ iff $\exists M, N \geq 0$ such that $$\lvert f(n) \rvert \leq M \lvert g(n) \rvert \quad \forall n \geq N$$ In this case, $f(n) = n^k$ and $g(n) = \sum_{i=0}^k a_i n^i$. Note that since all $a_i > 0$, we have $g(n) > 0$ on $n > 0$, so we can consider $$\frac{f(n)}{g(n)} = \frac{n^k}{\sum_{i=0}^k a_i n^i} = \frac{1}{a_k + \sum_{i=0}^{k-1} a_i n^{i-k}}$$ Observe that in the sum, we have $i-k < 0$ so that $$\sum_{i=0}^{k-1} a_i n^{i-k} \to 0 \text{ as } n \to \infty$$ and hence $$\frac{f(n)}{g(n)} \to \frac{1}{a_k} > 0 \text{ as } n \to \infty$$ This is sufficient (albeit not necessary) to give our result, since we know that by taking $N$ sufficiently large, we can bound the above by to be within $\varepsilon$ of $\frac{1}{a_k}$, and this gives the desired result by taking $M = \frac{1}{a_k} + \varepsilon$.

Answer 2

For non-negative functions equality $O(f)+O(g) = O(f+g)$ works in both directions and for $j>i$ we have $O(n^{i})+O(n^{j}) = O(n^{j})$. So:

$O(\sum_{i=0}^{k}a_i \cdot n^{i}) = \sum_{i=0}^{k}O(a_i \cdot n^{i}) = \sum_{i=0}^{k}O(n^{i}) = O(n^{k})$