Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
When completing exercises on Codility.com you submit your code to a server for analysis. You then receive a report containing the detected algorithm complexity of the code.
I was just wondering how it does this automatically - i.e. without any O(n) analysis?
This question came from our site for scientists using computers to solve scientific problems.
Probably only Codility knows for sure how they do it. But here is how I bet they do it.
First, they devise a set of test cases of varying sizes. They run your program on each test case and time how long it takes. This gives them a set of observations $(n_i,t_i)$, where $n_i$ is the size of the $i$th test case and $t_i$ is the time your program takes given that input. These can be viewed as a set of points in the 2D plane.
Second, they try to fit a curve to these points. For instance, they check whether a line appears to fit the points, or a quadratic, or a cubic. They probably have a library of a set of families of curves (e.g., $cn, $cn^2$, $c n \lg n$, $c \lg n$, and so on), and they check each to which ones are consistent with the observation. Then they output that one as the running time of your algorithm.
I would imagine some adjustments might be necessary. Rather than checking whether the points fit the curve, it might be necessary to check whether the points all fall below the curve. For instance, rather than checking whether there exists a constant $c$ such that $t_i \approx c n_i^2$ for all $i$, they might check whether there is a constant $c$ such that $t_i \le c n_i^2$ for all $i$ (with some constraints on $c$, e.g., $c \le 1000$). Out of all asymptotic running times that seem to be consistent with the observations, they select the asymptotically smallest one and output that one.
This approach has the advantage that it does not require analysis of source code. All they need is the ability to run your program and time its running time.
At the same time, this heuristic is definitely not foolproof: it can give the wrong answers in some cases. See How to fool the plot inspection heuristic?
There are some known methods for doing this, but the important thing to remember is, we can only ever get an upper or lower bounds, but we can't know if they're tight. In general, determining the complexity of an algorithm is undecidable, since if we could do that, we could solve the halting problem.
But there are some known techniques for doing this, that will work well in practice. For example, if there's a loop i from 0 to n-1, and the loop doesn't alter n, or have any break statements, we know the loop will run exactly n times.
For clear cut cases like this, you can compute this in a "top-down" way: you recursively determine the complexity of the loop body, determine the number of times the loop body is run. Things like this break down as soon as you do something more complicated (i.e. the number of times the loop is run changes, or doesn't depend directly on an input parameter), and there's really no way to know how they deal with hard cases without seeing their system.
Many systems are based on the idea of a system of recurrence relation: the complexity of a group of functions which call each other is determined, where the complexity of the functions called are left as variables. Then, you try to "solve" the system, or at least find an upper bound for it. This is particularly popular in functional languages.
Any bounds obtained this way aren't tight. What that means is, such an algorithm might return $O(\infty)$ even if the algorithm halts, return $O(2^n)$ even if the algorithm is polynomial (for upper bounds). Likewise, it might return $\Omega(1)$ for a lower bound, even if the algorithm is slower. These technically aren't incorrect as upper or lower bounds, they're just not tight.
It's also possible that they are doing some things empirically. For example, you could sample the run-time of the algorithm on a large number of inputs of different lengths. Then, you could set up a least-squares regression system for $n, n^2 ... \log n, n \log n, 2^n$, etc, and use some model-selection procedure to eliminate factors. This is pretty unreliable, though: lots of algorithms look polynomial for small inputs, and then turn exponential for larger inputs, plus there's lots of noise from the randomness of the procedure.
