1

Are constants always irrelevant even if they are large?

For example is O(10^9 * N) == O(N) ?

0

2 Answers 2

7

Big O describes how an algorithm scales; not, strictly speaking, how long it takes to execute.

In your example, if the time it takes to execute over 1 item is big, then it's going to take a (non-trivially) long time to execute the algorithm, even if it's applied to one item. But that algorithm will still increase in time linearly. So if you hit it with 100 items, you can expect it to take 100 times as long.

The same cannot be said of an O(n^2) algorithm; no matter how small the linear constant is, it's still going to eventually overtake the time it takes to execute the linear algorithm (as you increase N).

The linear constant is therefore ultimately irrelevant.

2
  • however that is only in theory, practicality wise the constant factor does matter when the n is bounded Apr 8, 2013 at 23:53
  • 2
    It can, yes. Presumably you're using Big O to get a read on how your program will behave under large loads. If you're only dealing with a relatively small number for N, it may not matter. Apr 8, 2013 at 23:54
4

It depends on what you are using your analysis to tell you.

  • If you are using it just to tell you how your algorithm scales up in the limit (i.e. as N goes to infinity), then the constants are not relevant.

  • If you are concerned (and you probably should be) with what the actual performance numbers are likely to be, then the constants are significant ... and the lower order terms could be significant too.

Big O is a way of simplifying the complexity analysis to answer one performance-related question. There are other questions that are equally relevant.

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