1
$\begingroup$

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

2 Answers 2

5

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.

  • 0
    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.2011-09-27
1

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

  • 0
    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 :)2011-09-27