Comment by Sebb767

This is a common misunderstanding of computational complexity: It does not measure runtime, but how runtime changes depending on the input. Take the following two algorithms to find the square root of an int:

  result=None
  for i in 0...INT_MAX
    if i*i==searched
      result=i
  return i

and

  for i in 0...searched
    if i*i==searched
      return i

The first algorithm is O(1), the second is O(sqrt(searched)). Despite this, the second will clearly be faster in actual execution time. However, if your number range changes from 0-100 to 100,000,000-250,000,000 , the former will still take the same time while the latter will take a lot longer. Now, in this example, this is quite obvious, but in the real world, you might encounter cases where a quadratic complexity solution is completely fine, until you have a lot of data and then suddenly your code slows to a crawl [0]. That's why we need computational complexity - it was never designed to perfectly measure or predict execution speed. This is also the reason constants are dropped in the notation.

For real world performance, benchmarking is the key. Computers are very complex beasts and there are a lot of potential speedups or slowdowns you might never think of - memory bank order, thermal throttling and compiler optimizability can drastically change the results, just to name a few. Computational complexity is totally fine as an angle to find new possible optimizations, but in the end, you need to compare it to the other approaches and see what actually works.

[0] https://news.ycombinator.com/item?id=21743424