Consider an^2 + bn + c
. I understand that for large n
, bn
and c
become insignificant.
I also understand that for large n
, the differences between 2n^2
and n^2
are pretty insignificant compared to the differences between, say n^2
and n*log(n)
.
However, there is still an order of 2 difference between 2n^2
and n^2
. Does this matter in practice? Or do people just think about algorithms without coefficients? Why?
Yes, constant factors matter very much in practice. Big-O notation is only the first step(albeit highly useful) in measuring the performance of an algorithm/program. An algorithm that takes only n^2 steps is certainly preferable to one that takes 2*n^2 steps, all things else being equal.
1
In the end the runtime [seconds] of the implementation of an algorithm is the deciding factor but the coefficients and the big-O notation help you in inventing efficient algorithms.
The big-O notation tells you how the algorithm behaves if the number of inputs/.. n changes dramatically (orders of magnitude). You mostly use it in a relative sense, i.e. increases polynomial, linear, nlog(n), …
If you compare two algorithms which have similar big-O terms you should include the coefficients. It could be that the worse order algorithm but with a better coefficient is actually faster for your typical data sets and you don’t want to miss that.
And finally in practise people often just take some implementations and let them run against each other. Gives you a practical view close to reality (used hardware and typical data sets) but dependent on the implementation, hardware and used data sets.
All together is the best.
What matters is subjective. However, you are correct that the coefficients are not of the first order of significance. The coefficients are often ignored mostly because there isn’t as much potential to improve an algorithm by worrying about them.
Consequently, I wouldn’t mind reworking code to get n^2
down to n*log(n)
. But going from 2n*log(n)
to n*log(2n)
is not something I’d be willing to make my code harder to read over.