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

Use the "ratio method" if you are trying to get a black-box estimate of the complexity. For instance: if you sit in a tight loop doing a fixed length job, like inserting a random record into a database, you record a timestamp at the end of each iteration. The timestamps will start to be farther apart as more data goes in. So, then graph the time difference between contiguous timestamps.

If you divide that graph by lg[n] and it continues to rise, then it's worse than lg[n]. Try dividing by: lg[n], n, nlg[n], nn, etc. When you divide by a function that is too high of an estimate, then plot will trend to zero. When you divide by a function that is too low, then the plot will continue to climb. When you have a good estimate, then there is a point in your data set at which you can place an upper and lower bound where the graph wanders around in for as far out as you care to check.

Answer 2

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 3

Suppose you run the following in a loop. At iteration i = 0, 1, 2, ...., for some fixed n_0 > 0 and very large n, you sample the function at 2 i + n_0 equi-distanced (up to rounding) points in the range 1, ..., n. You then do either one of the following or a combination of both:

1. Train a spline using the even points and test it on the odd points (and also vice versa). Decide the iteration is enough if the l2 error is below some threshold.

2. Train a spline using all the points, and test it on the values at, say 2n. Again, decide the iteration is enough if the l2 error is below some threshold.

Point 1. emphasizes the interpolation error, and point 2. emphasizes the extrapolation error. Realistically speaking, I think you will at best be able to identify functions described by a spline.

---

Depending on the fitting method you use, you might need to fit some meta-parameters for the spline method. In this case, you might need to use more than ~2 i samples per iteration, as you might need to use some of them for parameter-tuning cross validation.

Answer 4

First things first, I don't know of an accepted, "scientific" way to scale repetitions and problem size to achieve faster, more accurate time-vs-size plots, so I cannot say anything on the matter.

Other than that, for a better measurement of time complexity I would suggest to measure the average execution time for a fixed size and compare it with the average execution time measured in the previous cycle. After that you increase the size of the input data and repeat the measurement.

This is similar to one of the methods used in Numerical Analysis to estimate errors of numerical methods. You just adapt it to estimate the average error in the execution time of the implementation of your algorithm.

So, to cut it short:

1. Pick a size for the input data.
2. Run the implementation of the algorithm.
3. Calculate the average execution time.
4. If you have a previous calculation of the average execution time then compare it with the current execution time, else repeat from point 2.
5. If difference is greater than or equal to a certain (previously defined) threshold quantity then repeat from point 2.
6. Increase the size of the input data.
7. Repeat from point 2.

Let me know if something is unclear.

Answer 5

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.