Why two O(n) programs are same? Do constants matter? [duplicate]

Question

Possible Duplicate:
Complexity. Why dont constants matter?

I have a simple question regarding complexity of a code/algorithm. I understand the basic complexity concepts pretty well, such as order of growth with respect to input, why O(n) is better than O(n^2) etc. However, I am not sure if constants really matter or not because it seems to me that they should but no one ever considers them or talks about them. Can you improve a code with same complexity. Lets say I have a code with some order complexity lets say O(n). Lets say this code runs in 10 mins for certain input. What if I repeat the code twice and now the code runs in 20 mins. 20 mins over 10 mins is a big deal although the complexity is the same. Do these things matter or not, regardless of identical complexity? If not why? If yes, why? Please explain.

Answer 1

In theoretical complexity analysis, coefficients do not matter at all. In practice, they matter a great deal. This is why almost everyone still uses the (exponential complexity) simplex algorithm instead of (polynomial complexity) interior point algorithms for optimization problems.

If you're doing algorithm analysis and want to know the O() behavior, then constants are irrelevant. If you want to know which piece of code will run faster for a particular range of problems, then everything matters.

Answer 2

I think you are mixing the real concept of complexity with different example of performance. By complexity, what we mean is: if n grows, what is the order of processing steps growth.

Say for example, you are performing linear search and your order in this case is O(n). What des it mean here that: if n = 5, and it takes 5 seconds then for n=10, it will take 10 seconds i.e. relationship is linear.

It doesn't make difference, if order was O(5n) i.e. you same search takes 25 seconds for n=5, then for n=10, it will take 50 seconds. I can still say, its O(n) i.e. directly dependent.

Same example goes with sort algorithms who are O(n^2).

In your example, the mentioned improvement does matter but it doesn't change the order of complexity i.e. the relationship. If we can reduce the processing time by two times, it's a big improvement provided n is a high number e.g. time was reduced from 20 minutes to 10 minutes. If you change you algorithm to alter the relationship of time taken with the grown of n, then O(n) will also changed :)