Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
6  
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

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Thanks for that extremely clear explanation. Now I don't know if I should accept your answer.. the one above hit it home too :) –  Imray Jan 18 '13 at 5:13
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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