5
$\begingroup$

TL;DR: Do you know of a method/system that can determine the run time complexity of code automatically?

At our university we have a system in place that allows students to submit their code and get feedback on whether or not they satisfy the functional requirements of the exercise. This is excellent and works well for many of our courses, especially the introductory courses.

We also use it for courses that teach more advanced algorithmic concepts, focusing on run time. We have exercises that ask them to implement for example dynamic programming solutions in $O(n^2)$ time. Currently we use the automated tests to check for the functional requirements and have some tests with larger datasets and a time out to hopefully distinguish between $O(n^3)$ and $O(n^2)$ solutions.

Perhaps to nobody's surprise this system is not perfect, with some students optimising the wrong parts of their code to hand in an $O(n^3)$ (or worse) solution and get it through the tests. Thus for the graded assignments our TAs also check all of these by hand to make sure the solution is really $O(n^2)$ and they deduct some points if it is not.

My question is, do you know of systems or methods that can automatically check the run time complexity of code (in terms of big-O), rather than the actual run time (in seconds)?

In case this is relevant: the programming language used at our university is Java.

(NB: I've seen this question and appreciate the concerns about including this in grading. For introductory courses I would not do this. For the courses that focus on finding the most efficient algorithm to solve problems however it is one of the learning objectives :))

$\endgroup$
  • 4
    $\begingroup$ Rice's Theorem states that any non trivial semantic property is undecidable. A trivial property is a property that either holds for all programs or for none of them. A semantic property is a property of the behaviour of the program, not the "input-output". The property "does the algorithm take O(n^2) time?" is thus a non-trivial semantic property and it follows that it is undecidable in general and no such tool can exist. $\endgroup$ – Bakuriu Aug 21 at 18:24
6
$\begingroup$

Buffy is provably correct (no risk needed!) that it is impossible to do it with automated code analysis, as this is an attempt to figure out when a program will finish (i.e. the halting problem.)

You can get a very good guess, however, by using a few (very) differently sized input data sets, run the program on each one multiple times, and observe the results on a graph. This is fairly trivial for a human, and takes very little time. It may be less trivial for an automated statistical analysis, but I will defer to other who know more about such things to decide whether that is possible or not.

$\endgroup$
  • $\begingroup$ Unlike Buffy, you missed in general when stating that it's impossible. $\endgroup$ – Bergi Aug 21 at 22:30
  • $\begingroup$ @Bergi Just like Bogosort doesn't in general run in linear time. ;-) $\endgroup$ – Ben I. Aug 21 at 23:03
4
$\begingroup$

I'll accept a bit of risk here, but claim that this isn't possible in general unless the student writes very naive code. But in the courses for which you want to use it, that doesn't seem likely.

Imagine a linear algorithm implemented as two nested loops. The outer loop depends on the "n" that you are interested in, say the length of an array. The inner loop does not, but in some non obvious way. For example the inner loop may have a fixed (or bounded) number of iterations where the bound isn't obvious at that place in the program. This would be difficult to detect in general, and the analysis might report quadratic rather than linear if the code is a bit obfuscated.

A similar sort of (looking) program with an inner loop somewhat independent of the outer loop might result in a cubic run time algorithm but with only two loops.

I could probably come up with a recursive example as well (usual consulting rates apply).

The problem is that determining the complexity automatically would require a semantic analysis of the code deeper than that done by compilers. I think that might be possible in principle, but I doubt that such an analysis could be executed in a reasonable time. It might even be equivalent to the halting problem.

Some types of complexity can be statically analyzed of course. I use cyclotomic complexity as a measure of program quality and there are auto checkers for that.

$\endgroup$
  • $\begingroup$ That sounds fair, thanks to you both Buffy and Ben! :) I realise that what I'm asking is not trivial and may even be impossible. But I would be happy with something that can give me good guesses. Also I aware of the halting problem, but am not convinced it is an issue for the relatively small programs we have here. Note that I can already recognise looping programs as they do not pass the functional tests, and that even something that simply counts loops and thus over estimates could provide a nice starting point. $\endgroup$ – MrHug Aug 21 at 12:36
  • $\begingroup$ Probably not possible. It would likely both over and under estimate in some (different) cases. BTW, I once implemented an exponential time algorithm in production code because the size of the measured quantity could only be small enough to be irrelevant. Some people thought that was crazy but it worked. $\endgroup$ – Buffy Aug 21 at 12:39
  • $\begingroup$ "It might even be equivalent to the halting problem." – Rice's Theorem, actually, but same difference. $\endgroup$ – Jörg W Mittag Aug 21 at 21:39

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.