While this cannot be done for all cases (unless you start your own code analyzer and look at loops and what affects their values, etc.), you can still do this as a black box test with upper binding time . That is, to have some variable that is set to determine that as soon as the program runs this time, it is considered to be running forever.
From this, your code will look like this one (quick and dirty code, sorry, this is a bit detailed, and the math can be disabled for more power, which I have not tested).
It can be improved by using a given 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 and any other two inputs and define all the method duration patterns.
I am sure that there are much better (or rather, more accurate) methods for calculating O between a set of given numbers than shown here (which does not take into account too much time between elements).
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.
What the magic method shows is probably O(N^2) for these inputs +/- 2% of the variance
and one more result:
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)
What the magic method shows is probably O(N^3) for given inputs +/- 2% of the variance
Thus, it is possible to programmatically determine the complexity of the algorithm, you need to make sure that you do not enter any additional work that makes it be longer than you think (for example, when creating all the input data for the function, you have a time reference).
In addition to this, you also need to remember that it will take considerable time to try a large series of possible values and return how long it took, a more realistic test is simply to call your function on a large realistic top and determine if there is enough response time for your use.
You probably need to do this only if you are testing a black box without source code (and cannot use something like Reflector to view the source), or if you need to prove to PHB that the encoded algorithms are as fast as possible ( ignoring improvements in constants), as you say.