I am learning algorithms. So, I came along with something very interesting.

The asymptotic bound of linear function $an+b$ is $O(n^2)$ for all $a>0$.

This is same as for $an^2 + bn + c$. But shouldn't it be different?

  • 2
    $\begingroup$ Welcome! This is incomprehensible. What is the asymptotic bound of an equation (note that you don't give an equation). What do you mean by "This is same that of not so surprising"? I tried to edit it. $\endgroup$ – Raphael Sep 29 '12 at 20:29
  • $\begingroup$ Sometimes people write that $f = O(g)$ when they are being sloppy with / abusing their notation. By '$=$' they really mean '$\in$' and by $O$ they mean something more like $\Theta$. $\endgroup$ – Joe Sep 30 '12 at 1:36
  • $\begingroup$ Crosspost on programmers.SE $\endgroup$ – phant0m Sep 30 '12 at 17:59

$O$ only gives an upper bound; see also here. Clearly, $n^2$ is -- up to a constant factor -- an uppper bound for linear functions.

In fact, you can prove that

$n^{k_1} \in O(n^{k_2})$ for all $k_1 \leq k_2$.

Together with

$n^{k_1} + n^{k_2} \in O(n^{\max \{k_1,k_2\}})$ for all $k_1,k_2$

and the obvious

$cn^k \in O(n^k)$ for all $c,k$,

you get a general version of your statement.


$\mathcal{O}(g)$ (read Big oh of $g$) is a formalization of the idea that a function becomes nearly proportional to another one as we evaluate it at large values. Take for example the function $f(n) = 1000 + n + n^2$. For small values of $n$, most of the cost is coming from the constant $1000$; as $n$ becomes larger, the term $n$ contributes more to the cost. As $n$ becomes even larger, $n^2$ becomes more important to the point that most of the cost is coming from $n^2$. Therefore $f(n)$ becomes nearly proportional to $n^2$ as $n$ gets larger.

$\mathcal{O}$ is the set of functions that grow no faster than $g$ (times some constant). $n$ grows no faster than $n^2$ therefore it's in $\mathcal{O}(n^2)$, $n^2$ grows no faster than $n^2$, therefore $n^2$ is in $\mathcal{O}(n^2)$. The function in the previous paragraph is in $\mathcal{O}(n^2)$. In fact, any polynomial of degree $p$: $c_0 + c_1n^1 + c_2n^2 + \dots + c_pn^p$ is in $\mathcal{O}(n^p)$.

To prove that a function $f(n)$ is in $\mathcal{O}(g(n))$, you have to find constants $n_0$ and $c$ such that for large values of $n$ (means when $n$ >= $n_0$), it's always the case that $f(n) \le cg(n)$.

Let's prove that every polynomial is on the order of its highest degree term (on the order of is the same as saying in big oh of). Let $f(n) = c_0 + c_1n^1 + c_2n^2 + \dots + c_pn^p$ be a polynomial function. Let $c_{max} = \max\{c_0, \dots, c_p\}$.

We have $$f(n) \le c_{max}(p+1)n^p$$ We can set our constant $c$ to $c_{max}(p+1)$. Now we have to find $n_0$, that is for what values of $n$ does the inequality hold. Well, if $n=1$ the inequality holds so we can choose $n_0$ to be $1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.