2
$\begingroup$

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)$?

$\endgroup$
  • 6
    $\begingroup$ short answer yes $\endgroup$ – AJed Jan 17 '13 at 21:18
  • $\begingroup$ 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. $\endgroup$ – Khaur Jan 18 '13 at 10:44
8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Being needlessly pedantic (we often must for introductory questions), but it is only "no" if $a > 0$. $\endgroup$ – Artem Kaznatcheev Jan 18 '13 at 5:25
  • $\begingroup$ @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. $\endgroup$ – David Jan 18 '13 at 6:49

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.