Can a program calculate the complexity of an algorithm?

Question

Is there any way to compute the time complexity of an algorithm programatically? For example, how could I calculate the complexity of a fibonacci(n) function?

Answer 1

The undecidability of the halting problem says that you can't even tell if an algorithm terminates. I'm pretty sure from this it follows that you can't generally solve the complexity of an algorithm.

Answer 2

While it's impossible to do for all cases (unless you run your own code parser and just look at loops and what impacts on their values and such), it is still possible to do as a black box test with an upper bound time set. That is to say, have some variable that is set to determine that once a program's execution passes this time it's considered to be running forever.

From this your code would look similar to this (quick and dirty code sorry it's a little verbose and the math might be off for larger powers I haven't checked).

It can be improved upon by using a set array of input values rather than randomly generating some, and also by checking a wider range of values, you should be able to check any input versus any other two inputs and determine all the patterns of method duration.

I'm sure there are much better (namely more accurate) ways to calculate the O between a set of given numbers than shown here (which neglects to relate the run time between elements too much).

static void Main(string[] args)
{
    var sw = new Stopwatch();

    var inputTimes = new Dictionary<int, double>();

    List<int> inputValues = new List<int>();
    for (int i = 0; i < 25; i++)
    {
        inputValues.Add(i);
    }

    var ThreadTimeout = 10000;
    for (int i = 0; i < inputValues.Count; i++)
    {
        int input = inputValues[i];
        var WorkerThread = new Thread(t => CallMagicMethod(input)) { Name = "WorkerThread" };
        sw.Reset();
        Console.WriteLine("Input value '{0}' running...", input);
        sw.Start();
        WorkerThread.Start();
        WorkerThread.Join(ThreadTimeout);
        sw.Stop();
        if (WorkerThread.IsAlive)
        {
            Console.WriteLine("Input value '{0}' exceeds timeout", input);
            WorkerThread.Abort();
            //break;
            inputTimes.Add(input, double.MaxValue);
            continue;
        }
        inputTimes.Add(input, sw.Elapsed.TotalMilliseconds);
        Console.WriteLine("Input value '{0}' took {1}ms", input, sw.Elapsed.TotalMilliseconds);

    }

    List<int> indexes = inputTimes.Keys.OrderBy(k => k).ToList();

    // calculate the difference between the values:
    for (int i = 0; i < indexes.Count - 2; i++)
    {
        int index0 = indexes[i];
        int index1 = indexes[i + 1];
        if (!inputTimes.ContainsKey(index1))
        {
            continue;
        }
        int index2 = indexes[i + 2];
        if (!inputTimes.ContainsKey(index2))
        {
            continue;
        }

        double[] runTimes = new double[] { inputTimes[index0], inputTimes[index1], inputTimes[index2] };

        if (IsRoughlyEqual(runTimes[2], runTimes[1], runTimes[0]))
        {
            Console.WriteLine("Execution time for input = {0} to {1} is roughly O(1)", index0, index2);
        }
        else if (IsRoughlyEqual(runTimes[2] / Math.Log(index2, 2), runTimes[1] / Math.Log(index1, 2), runTimes[0] / Math.Log(index0, 2)))
        {
            Console.WriteLine("Execution time for input = {0} to {1} is roughly O(log N)", index0, index2);
        }
        else if (IsRoughlyEqual(runTimes[2] / index2, runTimes[1] / index1, runTimes[0] / index0))
        {
            Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N)", index0, index2);
        }
        else if (IsRoughlyEqual(runTimes[2] / (Math.Log(index2, 2) * index2), runTimes[1] / (Math.Log(index1, 2) * index1), runTimes[0] / (Math.Log(index0, 2) * index0)))
        {
            Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N log N)", index0, index2);
        }
        else
        {
            for (int pow = 2; pow <= 10; pow++)
            {
                if (IsRoughlyEqual(runTimes[2] / Math.Pow(index2, pow), runTimes[1] / Math.Pow(index1, pow), runTimes[0] / Math.Pow(index0, pow)))
                {
                    Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N^{2})", index0, index2, pow);
                    break;
                }
                else if (pow == 10)
                {
                    Console.WriteLine("Execution time for input = {0} to {1} is greater than O(N^10)", index0, index2);
                }
            }
        }
    }

    Console.WriteLine("Fin.");
}

private static double variance = 0.02;

public static bool IsRoughlyEqual(double value, double lower, double upper)
{
    //returns if the lower, value and upper are within a variance of the next value;
    return IsBetween(lower, value * (1 - variance), value * (1 + variance)) &&
        IsBetween(value, upper * (1 - variance), upper * (1 + variance));
}

public static bool IsBetween(double value, double lower, double upper)
{
    //returns if the value is between the other 2 values +/- variance
    lower = lower * (1 - variance);
    upper = upper * (1 + variance);

    return value > lower && value < upper;
}

public static void CallMagicMethod(int input)
{
    try
    {
        MagicBox.MagicMethod(input);
    }
    catch (ThreadAbortException tae)
    {
    }
    catch (Exception ex)
    {
        Console.WriteLine("Unexpected Exception Occured: {0}", ex.Message);
    }
}

And an example output:

Input value '59' running...
Input value '59' took 1711.8416ms
Input value '14' running...
Input value '14' took 90.9222ms
Input value '43' running...
Input value '43' took 902.7444ms
Input value '22' running...
Input value '22' took 231.5498ms
Input value '50' running...
Input value '50' took 1224.761ms
Input value '27' running...
Input value '27' took 351.3938ms
Input value '5' running...
Input value '5' took 9.8048ms
Input value '28' running...
Input value '28' took 377.8156ms
Input value '26' running...
Input value '26' took 325.4898ms
Input value '46' running...
Input value '46' took 1035.6526ms
Execution time for input = 5 to 22 is greater than O(N^10)
Execution time for input = 14 to 26 is roughly O(N^2)
Execution time for input = 22 to 27 is roughly O(N^2)
Execution time for input = 26 to 28 is roughly O(N^2)
Execution time for input = 27 to 43 is roughly O(N^2)
Execution time for input = 28 to 46 is roughly O(N^2)
Execution time for input = 43 to 50 is roughly O(N^2)
Execution time for input = 46 to 59 is roughly O(N^2)
Fin.

Which shows the magic method is likely O(N^2) for the given inputs +/- 2% variance

and another result here:

Input value '0' took 0.7498ms
Input value '1' took 0.3062ms
Input value '2' took 0.5038ms
Input value '3' took 4.9239ms
Input value '4' took 14.2928ms
Input value '5' took 29.9069ms
Input value '6' took 55.4424ms
Input value '7' took 91.6886ms
Input value '8' took 140.5015ms
Input value '9' took 204.5546ms
Input value '10' took 285.4843ms
Input value '11' took 385.7506ms
Input value '12' took 506.8602ms
Input value '13' took 650.7438ms
Input value '14' took 819.8519ms
Input value '15' took 1015.8124ms
Execution time for input = 0 to 2 is greater than O(N^10)
Execution time for input = 1 to 3 is greater than O(N^10)
Execution time for input = 2 to 4 is greater than O(N^10)
Execution time for input = 3 to 5 is greater than O(N^10)
Execution time for input = 4 to 6 is greater than O(N^10)
Execution time for input = 5 to 7 is greater than O(N^10)
Execution time for input = 6 to 8 is greater than O(N^10)
Execution time for input = 7 to 9 is greater than O(N^10)
Execution time for input = 8 to 10 is roughly O(N^3)
Execution time for input = 9 to 11 is roughly O(N^3)
Execution time for input = 10 to 12 is roughly O(N^3)
Execution time for input = 11 to 13 is roughly O(N^3)
Execution time for input = 12 to 14 is roughly O(N^3)
Execution time for input = 13 to 15 is roughly O(N^3)

Which shows the magic method is likely O(N^3) for the given inputs +/- 2% variance

So It is possible to programatically determine the complexity of an algorithm, you need to make sure that you do not introduce some additional work which causes it to be longer than you think (such as building all the input for the function before you start timing it).

Further to this you also need to remember that this is going to take a significant time to try a large series of possible values and return how long it took, a more realistic test is to just call your function at a large realistic upper bound value and determine if it's response time is sufficient for your usage.

You likely would only need to do this if you are performing black box testing without source code (and can't use something like Reflector to view the source), or if you have to prove to a PHB that the coded algorithms are as fast as it can be (ignoring improvements to constants), as you claim it is.