4

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?

Improve this question

3 Answers 3

Reset to default
4

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.

Improve this answer
1
  • 2
    Counterpoint: yes, but not all steps are equal, even from machine to machine. An operation might take 5 cycles on one CPU and just one on another. Caches are also critical, and often an algorithm that uses a linked list will be slower than an array-based program, even if it uses half the operations.
    – raptortech97
    Commented Dec 1, 2014 at 4:39
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.

Improve this answer
0

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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.