System to validate run time complexity requirements

Question

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 :))

Answer 1

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.

Answer 2

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.