0
$\begingroup$

I am extremely new a calculating big O notation and I am extremely confused by this quote from the book Discrete Mathematics and Its Applications

For instance, if we have two algorithms for solving a problem, one using 100n^2 + 17n + 4 operations and the other using n^3 operations, big-O notation can help us see that the first algorithm uses far fewer operations when n is large, even though it uses more operations for small values of n, such as n = 10.

So if n is less than 10 (E.G. 5), are we just going to substitute it like:

100*5^2 + 17*5 + 4

But this is larger than 5*3.

How to correctly calculate these kind of functions? Is calculus needed for this?

$\endgroup$
2
  • $\begingroup$ Anyway, $a_n=O(b_n)$ does not even mean that $b_n\geqslant a_n$ for even one single $n$. Let me suggest to read and digest some source on the $O$ notation (say, the WP page). $\endgroup$
    – Did
    Nov 21, 2015 at 10:20
  • $\begingroup$ "big-O notation can help us see that the first algorithm uses far fewer operations when n is large" The formulation is rather unfortunate since the big-O statement does NOT mean that (some confusion with a small-o statement might be looming here). $\endgroup$
    – Did
    Nov 21, 2015 at 10:23

2 Answers 2

1
$\begingroup$

You don't need to calculate anything. Just note: In a polynomial the fastest growing (decreasing) term will always be the monomial of highest order. For a general polynomial

$a_0+a_1x+...+a_nx^n$

this is the $a_nx^n$.

Meaning: For large values of n this term will dominate all the others so you could also just have a look at the highest order term in order to argue how the function behaves for large x, right? This is somehow what the quote from the book tells you. For large values of the variable (n in your case) the second algorithm will be very expensive (especially more expensive than the other algorithm). Imagine for example that the 2 algorithms (just exemplary) multiply matrices, and n is the dimension of the matrix.

Big O notation tells you, that for very large system you should use the first algorithm, as it is less expensive ($cn^2$ operations) than the other one ($cn^3$)

Edit: you can also take into consideration terms like ln(x) (very slow growing) or $e^x$ (very Very fast growing)

$\endgroup$
8
  • $\begingroup$ ok, I understand the highest order term part. But in terms of n^2 being faster than n^3, how does n^3 become faster than n^2 if n is a small value like 10? $\endgroup$ Nov 21, 2015 at 10:08
  • $\begingroup$ Well, if one algorithm needs $20n$ operations and another needs $n^2$ for doing something, this means that for very small n the cost of the first is much higher, right? Take $n=3$, so the first algorithm needs 60 operations whereas the second just needs 9. for small n the first is therefore more expensive. However. For large n the squared term will increase faster than the linear term, so for big n it's the other way round. Big O notation considers just the fastest growing term, so $x^n+1000x^{n-1}$ is in $O(x^n)$$ $\endgroup$ Nov 21, 2015 at 10:16
  • $\begingroup$ so this means, if there are functions like 100n^2 + 17n + 4, regardless of how many terms there are, I should ignore all terms except the largest? If we are comparing 100n^2 + 17n + 4 we really are just using 100n^2? $\endgroup$ Nov 21, 2015 at 10:29
  • $\begingroup$ In big O notation yes. You're even ignoring the factor 100, it's just $O(n^2)$ (for vey large n even the factor 100 doesn't matter anymore) $\endgroup$ Nov 21, 2015 at 10:32
  • $\begingroup$ "for very large n even the factor 100 doesn't matter anymore". But for small n, I used the 100 in my example and you used 20 to prove that in small values of n, 20n is more expensive than n^2. If we remove 20 from your example, how can we find the n value where n^2 starts getting more expensive than n? $\endgroup$ Nov 21, 2015 at 10:44
0
$\begingroup$

You're missing "when $n$ is large" in the cited quote, which means that there is some number such that any $n$ larger than that will always satisfy $n^3 > 100 n^2 + 17 n + 4$.

$\endgroup$
4
  • $\begingroup$ "which means that there is some number such that any nn larger than that will always satisfy..." Actually, no, this does not mean that. $\endgroup$
    – Did
    Nov 21, 2015 at 10:24
  • $\begingroup$ @Did: Yes I know that what I said isn't about big-O-notation, nor little-o-notation, but I thought of conveying the general idea first since that's the key point the asker is missing. $\endgroup$
    – user21820
    Nov 21, 2015 at 10:27
  • $\begingroup$ @Did: Perhaps you should write a better answer that I can upvote, since often Wikipedia is overwhelming for all readers except those who know what they're looking for. $\endgroup$
    – user21820
    Nov 21, 2015 at 10:28
  • $\begingroup$ In the present case, it is not. $\endgroup$
    – Did
    Nov 21, 2015 at 10:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .