Proof of big-O notation
- Given two real valued functions f and g: $$f(n)=O(g(n))$$ If $c>0$ and $n_0>0$: $f(n) \geq cg(n) \geq 0, \forall n\geq n_0$
From the definition it follows that for $n \geq 0$
$$a_0n^d + a_1n^{d-1} + a_2n^{d-2} + ... + a_d \leq |a_0|n^d + |a_1|n^{d-1} + |a_2|n^{d-2} + ... + |a_d|$$
$$\leq |a_0|n^d + |a_1|n^{d} + |a_2|n^{d} + ... + |a_d|n^{d}$$ $$\leq n^d(|a_0| + |a_1| + |a_2| + ... + |a_d|)$$ Let $c=|a_0| + |a_1| + |a_2| + ... + |a_d|$ and $n_0=1$ $$\Rightarrow g(n)\equiv n^d$$ $$\Rightarrow f(n)\equiv O(n^d)$$