Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is probably not the best worded question but here goes.

I've been reading a text book trying to get my head around time complexity.

I understand the most of it, but this example has threw me. Am I missing something or is the textbook simply wrong.

It has the following table:

$g(n)$, where $f(n) = O(g(n))$

  • $g(n) = 5 \to f(n) = O(1)$
  • $g(n) = 20n + 17 \to f(n) = O(n)$
  • $g(n) = 40n^2 + 3n - 10\to f(n) = O(n^2)$
  • $g(n) = 10n^3 + 26n^2 + 220 \to f(n) = O(n^3)$

I understand the first two cases: If ($g(n)$ is 5) time complexity is a constant. and if ($g(n)$ is $20n + 17$ then time complexity is $O(n)$ as constants are ignored.

What I'm not sure I understand is why the last two cases are equal to $O(n^2)$ and $O(n^3)$ respectively.

From my math understanding and ignoring constants it should be $O(n^3)$ and $O(n^5)$ respectively and not what was in the text book.

Some enlightenment would be great, I've searched all over for my answer. Thanks

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

The condition for $40n^2+3n-10$ being $O(n^2)$ is that there is some constant $K$ such that $40n^2+3n-10 < Kn^2$ if only $n$ is large enough.

To see that this is the case, rewrite it as $$40n^2+3n-10 = n^2\left(40+\frac{3}{n}-\frac{10}{n^2}\right)$$ The parenthesis on the right-hand-side goes towards 40 when $n\to\infty$, so you can use $K=41$ (or 40.0000001 or anything that is larger than 40).

The lesson to take home is that only the degree of a polynomial matters for its big-O classification.

share|improve this answer
    
That right there is a great answer, and you've jut helped me understand big O, finally, thanks a lot :D I appreciate it, I really do. –  user6701 Sep 27 '11 at 21:06
add comment

Your conclusion is incorrect because you are multiplying the powers of $n$ modulo constants. The leading order term of the polynomial determines the complexity because it dominates the other terms in value for large $n$. Using your notation, the complexity of a polynomial $p(n)$ of degree $m$ is $O(n^m)$.

share|improve this answer
    
Thanks for the answer, and that helps a lot actually. However I'm still not 100% on why in the example above, these values for g(n) are given. Maybe i'm missing the point and should find a more thorough textbook :) –  user6701 Sep 27 '11 at 21:01
add comment

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.