Can Big(O) be affirmed by measurement?

Question

Let's say you have designed an algorithm which you might think runs in O(n). If I measure the time it runs with 1000 input and then increase the input 10x and then measure again. Can I infer that O(n) is correct iff run time is almost 10 times the first try?

How stupid would this be? Obviously repeating the test would give a better accuracy but I wanna know if this makes sense at all.

Answer 1

On the contrary to the other answer, I will say "no". However, you can get a pretty good guess (not even an estimate as it is not appropriate here). This is probably what is meant by "often".

The thing is, that you never know the constant factors. Big Oh is asymptotic behaviour (in infinity), this is a very very useful to drop everything except for the most growing term. So mathematically you cannot confirm your assumption.

Firstly, here is plenty of algorithms and use-cases when asymptotic behaviour is not useful in real-life applications. Simply because "typical use-case" input distribution falls off. This is more often case. And you could still test/"estimate" it.

But there is also a case where the best algorithm has such big constant factors it is not applicable on modern systems. The best example I know are large number multiplication algorithms.

However, there are systems that "approximate" (better said guess) complexity class of an algorithm. I am not sure whether Codility_ measure it or get their guess by code analysis but they are able to do it: https://app.codility.com/public-report-detail/.

What could be done do is to run an algorithm, and change input size, run tests and fit the data to model. It's quite simple. Then you can say that for tested input range the algorithms behaves as O(class(n)). (This might have a practical meaning valuable even more than theoretical asymptotic complexity.)

Note that choosing the testing points is not trivial. Basically if your algorithm behaves "fast" then you need to increase input size rate to the next class. E.g. if you have something like (100n+n!) you can go n={1,10,100} because it will kill execution time. However going n={1,2,3,4,5,6,7} won't pick up the n! part (ok 7! is 5040 but for n^2 it would be much harder).

Bottom line, getting a nice guess is certainly possible, but beyond most simple cases it can be tricky and hard to do, and sadly it is quite hard to tell if case is tricky or not.

Also, this discussion is purely theoretical, skipping hardware effects. I have heard said of algorithms that n^2 behaved better than n^log n because former was always (very) cache friendly, but don't take my word for it, I can't recall source.

Answer 2

Plotting input size against run-time for actual programs is an extremely helpful tool to let you see how your code actually performs. In general, it's dangerous to think you can use it to infer complexity.

Here's a practical example of one way it breaks down.

Good quick-sort implementations pivot the array into three parts: less than the pivot, equal to the pivot, and greater than the pivot. That means that quick-sorting a random array 64-bit ints (in fact, sorting a random array of any fixed-size datatype) uses O(n) comparisons because eventually every sub-array will be constant.

Unfortunately, you can't see this empirically: if you plot n against the number of comparisons, the graph looks like n*log(n) until the input array gets much larger than 2^64 elements. Even if you had enough memory, your programming language probably doesn't allow you to index arrays of that size.

This also example demonstrates that empirical measurement gives you interesting data (that the code performs like n*log(n) on actual input), and complexity gives you a theoretical but practically useless fact about asymptotic growth being linear.

Answer 3

In addition to what others have said. Sometimes the average case and worst case may be different, and the worst case may be hard to find. A famous example is quicksort, with its O(n log n) average behaviour (abuse of the O notation?), and O(n^2) worst case behaviour. If you have been given a "black-box" algorithm (well, program), such worst cases may be hard to catch experimentally without the knowledge about the algorithm.