1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Agreed; this question is probably more appropriate for CS Stack Exchange. $\endgroup$ – Geoff Oxberry Oct 20 '15 at 19:51
  • 1
    $\begingroup$ It's hard to say because we don't know how the site works, but perhaps it does some empirical analysis. $\endgroup$ – Yuval Filmus Oct 20 '15 at 20:25
  • 1
    $\begingroup$ Are you asking what they do? We can not know. Are you asking what is possible? Well, nothing (if you want to never be wrong). $\endgroup$ – Raphael Oct 20 '15 at 20:55
  • $\begingroup$ <rant>If they really claim to always give you back an accurate $O$-class, then they prove why programmers need more CS training, and that they are probably not best qualified to certify programming skills.</rant> $\endgroup$ – Raphael Oct 20 '15 at 21:00
  • $\begingroup$ In the candidate report they sometimes give an $O$-class. Other times, they only show some timeouts similar to other coding challenges. So they probably do some pattern matching. Challenge: break the system! $\endgroup$ – Raphael Oct 20 '15 at 21:03
2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "we can only ever get an upper bound" -- Huh? We can't even get that, and I don't see why getting lower bounds would be any harder. $\endgroup$ – Raphael Oct 20 '15 at 20:57
  • $\begingroup$ Yeah, you're right, hopefully it's clearer now. $\endgroup$ – jmite Oct 20 '15 at 20:59
  • $\begingroup$ That still suggests we can get such bounds. We can't! $\endgroup$ – Raphael Oct 20 '15 at 21:01
  • $\begingroup$ We can, we just don't know if they're tight. I can always return $O(\infty)$ for an upper bound and $\Omega(1)$ as a lower bound. The procedure just then uses heuristics to see if these can be made tighter, but it can always return a correct (not tight) upper and lower bound. $\endgroup$ – jmite Oct 20 '15 at 21:04
  • $\begingroup$ Sure, $\Omega(1)$ is always possible, and "never" tight. It's debatable whether $O(\infty)$ even makes sense. If you allow it, sure -- these completely uninformative bounds can always be given. (But we know they are not tight, contrary to your statement) But not an epsilon more, in general. $\endgroup$ – Raphael Oct 20 '15 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.