if n was a
(n^2 + n) / 2 = 500000500000 (5.00001E+11)
(n^2) / 2 = 500000000000 (5E+11)
(n^2) = 1000000000000 (1E+12)
While the complexity gives us a way to predict a real-world cost (seconds or bytes depending on whether we are talking about time complexity or space complexity), it doesn't give us a number of seconds, or any other particular unit.
It gives us a degree of proportion.
If an algorithm has to do something n² times, then it will take n²×c for some value of c that is how long each iteration takes.
If an algorith has to do something n²÷2 times, then it will take n²×c for some value of c that is twice as long as each iteration takes.
Either way, the time taken is still proportional to n².
Now, these constant factors are not something we can just ignore; indeed you can have the case where an algorithm with O(n²) complexity does better than one with O(n) complexity, because if we are working on a small number of items then impact of the consant factors is greater and can overwhelm other concerns. (Indeed, even O(n!) is the same as O(1) for sufficiently low values of n).
But they are not what complexity tells us about.
In practice, there are a few different ways we can improve the performance of an algorithm:
- Improve the efficiency of each iteration: O(n²) still runs in n²×c seconds, but c is smaller.
- Reduce the number of cases seen: O(n²) still runs in n²×c seconds, but n is smaller.
- Replace the algorithm with one that has the same results, but lower complexity: E.g. if we could repalce something O(n²) to something O(n log n) and hence changed from n²×c₀ seconds to (n log n)×c₁ seconds.
Or to look at it another way, we've got
f(n)×c seconds being taken and you can improve performance by reducing
n or reducing what
f returns for a given
The first we can do by some micro-opts inside a loop, or using better hardware. It will always give an improvement.
The second we can do by perhaps identifying a case where we can short-circuit out of the algorithm before everything is examined, or filter out some data that won't be signficant. It won't give an improvement if the cost of doing this outweighs the gain, but it will generally be a bigger improvement than the first case, especially with a large n.
The third we can do by using a different algorithm entirely. A classic example would be replacing a bubble sort with a quicksort. With low numbers of elements we may have made things worse (if c₁ is greater than c₀), but it generally allows for the biggest gains, especially with very large n.
In practical use, complexity measures allow us to reason about the differences between algorithms precisely because they ignore the matter of how reducing n or c will help, to concentrate on examinging