Big-O complexity when c is a tiny fraction

Finding Big-O is pretty straightforward for an algorithm where $f(n)$ is

$$f(n) = 3n^4 + 6n^3 + 10n^2 + 5n + 4$$

The lower powers of $n$ simply fall off because in the long run $3n^4$ outpaces all of them. And with $g(n) = 3n^4$ we say $f(n)$ is $O(n^4)$.

But what would Big-O be if instead of 3 we were given a really small constant, for example $$f(n) = 0.0000000001n^4 + 6n^3 + 10n^2 + 5n + 4$$

Would we still say $f(n)$ is $O(n^4)$?

• short answer yes – AJed Jan 17 '13 at 21:18
• This shows one of the weaknesses of Big-O applied to algorithm complexity. Just because it's bigger in the very (very) long run doesn't mean it's better with reasonable input. – Khaur Jan 18 '13 at 10:44

Medium answer - yes. As you said for the previous case, in the long run $n^4$ outpaces all of them. This is still true despite the constant in front.

Check it out: plot.

Also, remember that $n^3$ and $n^4$ are both $O(n^4)$, and in fact are both $O(n^{10})$ because big-O is an upper bound. So you might ask "is there any tighter big-O bound on this function than $O(n^4)$, like $O(n^3)$, and the answer would be no.

Remember, when we write $f(x) = O(g(x))$ we are saying that there are two positive constants, $c$ and $x_0$ such that $|f(x)| \le c|g(x)|$ for all $x \ge x_0$. Asymptotic analysis is concerned with how functions behave in the limit.

Let's rewrite your function:

$$f(n)=an^4+6n^3+10n^2+5n+4$$

This function is $O(n^4)$. Your question is "Can we change the value of the constant $a$, in such a way that $f(n)$ is no longer $O(n^4)$?" The answer is no. For any $a$, we can choose $c$ and $n_0$ such that $|f(n)| \le c|n^4|$ for all $n \ge n_0$. In fact, you have already stated this:

The lower powers of $n$ simply fall off because in the long run $3n^4$ outpaces all of them.

This holds true regardless of the value of $a$ in the function. It may take "longer" for $an^4$ to outpace the other terms, but it eventually will.

• Being needlessly pedantic (we often must for introductory questions), but it is only "no" if $a > 0$. – Artem Kaznatcheev Jan 18 '13 at 5:25
• @ArtemKaznatcheev You are right to point this out. I believe that $f(n)$ being positive is often assumed/implied; in CS and algorithm analysis $n$ usually represents an input size so it doesn't make sense for it to be negative. But O notation describes the behavior of mathematical functions, not just algorithms, and the actual definition includes absolute values -- I have updated my answer to reflect this. – David Jan 18 '13 at 6:49