Best practices for measuring the run-time complexity of a piece of code

Question

I have a gnarly piece of code whose time-efficiency I would like to measure. Since estimating this complexity from the code itself is hard, I want to place it in a loop and time the results. Once enough data-points (size -> time) are gathered, I can see which curve fits best.

Repeating operations a number of times with random input data of a given size can smooth out fluctuations due to the OS deciding to multitask at bad moments, yielding more precise times. Increasing the size of the problem provides more points, ideally well spaced.

My test-code works fine (initial, non-timed warm-up loop to decrease load-times; and then, starting from a size of 10, scaling up to 1000000 in increments of a factor of 10%, repeating runs until 5s have elapsed or 5 full runs have finished). However, I arrived at these numbers by guess-work.

Is there an accepted, "scientific" way to scale repetitions and problem size to achieve faster, more accurate time-vs-size plots? Is there code out there (or libraries) that can scaffold all the boring bits, and which I should have been aware of before rolling-my-own? In particular, I can think that, when bumps in timings are found, more measures could be warranted -- while relatively smooth readings could simply be considered "good enough".

Edit

I am aware of the classical method of calculating big-O complexity. It works fine for self-contained algorithms with a nice representative operation (say, "comparisons" or "swaps"). It does not work as advertised when those conditions are not met (example: the compile-time C++ template instantiation costs of LLVM, which is a large and complex and where I do not know what the relevant representative operation would be). That is why I am treating it as a black box, and trying to measure times from the outside instead of by code inspection.

Answer 1

Measuring the time complexity can be very difficult (if it is possible at all) and I never saw this in algorithm papers. If you cannot calculate the time-complexity from (pseudo-) code or the algorithm description, then maybe you can use a heuristic to simplify the analysis.

Maybe you can also calculate the complexity of some parts of the algorithm and ignore some other parts if they have obviously a much smaller complexity.

If nothing helps, the normal way would to show how the algorithm scales on an machine, just as you wrote. But there are many things that effect the results. Just to notice some of them:

• Memory types: If your input is small enough to fit into the L1 cache, your algorithm runs very fast, just because the memory is fast. If your input gets bigger, so it doesn't fit into L1 cache any more, it is stored in the L2 cache and if it gets even bigger it is stored in the RAM. And each time your program slows down by a huge factor (in addition to the factor of the growing input). The worst is, when it gets so big that the algorithm has to store some of thin input at your hard disc.
• Multitasking: If your OS decides to hand over the CPU to an other program your algorithm seems to slow down. This is also hard to handle.
• Hardware: In big-O every operation counts as 1 unit of time. If your algorithm performs a lot of operations, that your CPU is optimized for, this also effects your measurement.
• Software: Software can effect your measurement the same way as hardware does. E.g. if you have a lot of big integer operations using a library, you can massively speed up the program by using GMP.
• Warmup: If you start measuring, you have to warmup the CPU first. Run the algorithm on a bigger input first (without measuring).
• Input cases: You can only run your program on some chosen or random generated input cases of a specific length. In most cases it is hard to tell (or just not possible) if the input causes a shorter or longer run-time. So maybe you test the wrong examples. If you us random inputs, you get more different results.

All in all: I think you can only get an idea, how your algorithm scales, but you cannot exactly get an upper bound of the complexity by measuring the run-time. Maybe this works for really small examples, but for bigger ones you will not get correct results.

The best you can do would be:

• Write down the exact hardware and software of the computer you use for measurement.
• Repeat the tests multiple times (in different orders)
• If you change hard or software you should start from the beginning.
• Only use inputs that are all stored in the same memory type, so skip all cases that fit into the cache.

This way you can see if changes have improved the algorithm or not and others can verify your results.

About the input:

• You should use worst case inputs, if possible. If you cannot say if an input is a worst case or not, you should use many different cases or random inputs (if possible).
• You have to run tests (for each input length), until the average of the run-times stabilizes.

Answer 2

I'm not aware of any software for this, or previous work done on it. And, fundamentally, I don't think you can get answers of the form "O(whatever)" that are trustworthy. Your measurements are noisy, you might be trying to distinguish nlog(n) operations from nsqrt(n) operations, and unlike a nice clean mathematical analysis, all of the dropped constants are still floating around messing with you.

That said, the process I would go through if I wanted to come up with a best estimate:

1. Making sure I record as much information as possible through the whole process, I'd run the thing I want to measure on as many inputs (and sizes) as I could before I got bored. Probably overnight. Repeated measurements for each input and size.
2. Shovel the input size to time data into a trial copy of Eureqa and see what pops out.
3. If I'm not satisfied, get more data, continue to shovel it into Eureqa and see if the situation is improving.
4. Assuming Eureqa doesn't give an answer I like before I get bored of it consuming all of my CPU time and power, I'd switch over to Bayesian methods.
5. Using something like pymc I'd attempt to model the data using a bunch of likely looking complexity functions. (n, n^2, n^3, n^3, n*log(n), n^2*log(n) n^2*log(n)^2, etc, etc, etc).
6. Compare the DIC (smaller is better) of each model, looking for the best few.
7. Plot the best few, look for spots where data and model disagree.
8. Collect more data near disagreements. Recompute the models.
9. Repeat 5-8 until bored.
10. Finally, collect some new data points at larger input sizes, see which model(s) best predict those data points.
11. Choose to believe that one of them is true enough.