Easiest way to determine time complexity from run times

Question

Lets suppose I am trying to analyze an algorithm and all I can do is run it with different inputs. I can construct a set of points (x,y) as (sample size, run time). I would like to dynamically categorize the algorithm into a complexity class (linear, quadratic, exponential, logarithmic, etc..) Ideally I could give an equation that more or less approximates the behavior. I am just not sure what the best way to do this is.

For any degree polynomial I can create regression curves and come up with some measure of fitness, but I don't really have a clue how I would do that for any nonpolynomial function. It is harder since I don't have any previous knowledge of what shape I should try to fit.

This may be more of a math question than a programming question, but it is very interesting to me. I'm not a mathematician, so there may be a simpler established method to get a reasonable function from a set of points that I just don't know about. Does anyone have any ideas for solving a problem like this? Is there a numerical library for C# that could help me crunch the numbers?

Answer 1

Curve fitting used to be an art, but is now somehow decadent :) (That's a joke for the physicists around)

A lot of progress has been made, that allows simple mortals to guess (some) non trivial functional dependencies.

I'll not enter into a description of the methods and limitations, but instead I'll refer you to eureqa, which is a very nice piece of software developed at Cornell.

Eureqa (pronounced "eureka") is a software tool for detecting equations and hidden mathematical relationships in your data. Its goal is to identify the simplest mathematical formulas which could describe the underlying mechanisms that produced the data. Eureqa is free to download and use. Look for the program download, video tutorial, user forum, and other and reference materials.

I tried eureqa several times with very good results if the models are not too complicated. I think it is good enough for distinguishing between polynomials, logs and exponentials.

HTH!

Answer 2

Well there are not that many complexity classes you really care about, so let's say: linear, quadratic, polynomial (degree > 2), exponential, and logarithmic.

For each of these you could use the largest (x,y) pair to solve for the unknown variable. Let y = f(x) denote the runtime of your algorithm as a function of the sample size. Let's assume that f(1) = 0, and if it doesn't we can always subtract of that value y(1) from each of the y's, this just eliminates the constants in f(x). Let y(end) denote the last (and largest) value of y in your (x,y) data set.

At this point we can solve for the unknown in each canonical form:

f(x) = c*x
f(x) = c*x^2
f(x) = x^c
f(x) = c^x
f(x) = log(x)/log(c)

Since there is only a single unknown in each equation we can you any point to solve for it. Consider the following data generated from a polynomial of random degree > 2:

x = [ 1 2 3 4 5 6 7 8 9 10 ];
y = [ 0 6 19 44 81 135 206 297 411 550 ];

If we use the last point to solve for c for each possibility (assuming this would be the least noise estimate)

550 = c*10    -> c = 55
550 = c*10^2  -> c = 5.5
550 = 10^c    -> c = log(550)/log(10) ~= 2.74
550 = c^10    -> c = 550^(1/10) ~= 1.88
550 = log(x)/log(c) -> c = 10^(1/550) ~= 1.0042

We can now compare how well each of these functions fit the remaining data, here is a plot:

I'm new and I can't post images so look at the plot here: http://i.imgur.com/UH6T8.png

The true data is shown in the red asterisk, linear with green line, quadratic in blue, polynomial in black, exponential in pink, and the log plot in green with O's. It should be pretty clear from the residuals what function fits your data the best.