Answers.Body: <p>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. </p>
  
  <p>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. </p>
  
  <p>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. </p>
  
  <p>I could probably come up with a recursive example as well (usual consulting rates apply). </p>
  
  <p>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. </p>
  
  <p>Some types of complexity can be statically analyzed of course. I use <em>cyclotomic complexity</em> as a measure of program quality and there are auto checkers for that. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-21T12:36:55.677Z
Answers.Text: 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.
Answers.UserDisplayName: MrHug
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-21T12:39:22.923Z
Answers.Text: 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.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-21T21:39:44.903Z
Answers.Text: "It might even be equivalent to the halting problem." – Rice's Theorem, actually, but same difference.
Answers.UserDisplayName: Jörg W Mittag
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-21T10:50:04.253Z
Answers.LastActivityDate: 2019-08-21T10:50:04.253Z
Answers.UserDisplayName: Buffy
Answers.Body: <p>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 <em>when a program will finish</em> (i.e. the <a href="https://en.wikipedia.org/wiki/Halting_problem" rel="noreferrer">halting problem</a>.)</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-21T22:30:52.857Z
Answers.Text: Unlike Buffy, you missed *in general* when stating that it's impossible.
Answers.UserDisplayName: Bergi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-21T23:03:30.303Z
Answers.Text: @Bergi Just like Bogosort doesn't *in general* run in linear time.  ;-)
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-21T12:27:47.173Z
Answers.LastActivityDate: 2019-08-21T12:27:47.173Z
Answers.UserDisplayName: Ben I.
Body: <p><strong>TL;DR:</strong> Do you know of a method/system that can determine the run time complexity of code automatically?</p>
  
  <p>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.</p>
  
  <p>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 <span class="math-container">$O(n^2)$</span> 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 <span class="math-container">$O(n^3)$</span> and <span class="math-container">$O(n^2)$</span> solutions.</p>
  
  <p>Perhaps to nobody's surprise this system is not perfect, with some students optimising the wrong parts of their code to hand in an <span class="math-container">$O(n^3)$</span> (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 <span class="math-container">$O(n^2)$</span> and they deduct some points if it is not.</p>
  
  <p>My question is, do you know of systems or methods that can automatically check the run time <em>complexity</em> of code (in terms of big-O), rather than the actual run time (in seconds)?</p>
  
  <p>In case this is relevant: the programming language used at our university is Java.</p>
  
  <p>(NB: I've seen <a href="https://cseducators.stackexchange.com/questions/3199/incorporating-algorithmic-complexity-in-grading">this question</a> 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 :))</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-08-21T18:24:04.983Z
Comments.Text: [Rice's Theorem](https://en.wikipedia.org/wiki/Rice%27s_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.
Comments.UserDisplayName: Bakuriu
Tags: <algorithms><grading>
Title: System to validate run time complexity requirements
ThreadText: # System to validate run time complexity requirements
  
  (Asked by: username_0 on 2019-08-21)
  
  **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](https://cseducators.stackexchange.com/questions/3199/incorporating-algorithmic-complexity-in-grading) 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 :))
  
  **Tags:** algorithms, grading
  
  > **Comments:**
  > **username_1**: [Rice's Theorem](https://en.wikipedia.org/wiki/Rice%27s_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.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2019-08-21. Score: 6 | Accepted answer
  
  username_2 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](https://en.wikipedia.org/wiki/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.
  
  > **Comments:**
  > **username_5**: Unlike username_2, you missed *in general* when stating that it's impossible.  
  > **username_4**: @username_5 Just like Bogosort doesn't *in general* run in linear time.  ;-)  
  
  ---
  
  ### Answer by username_2 on 2019-08-21. Score: 4
  
  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.
  
  > **Comments:**
  > **username_0**: That sounds fair, thanks to you both username_2 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.  
  > **username_2**: 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.  
  > **username_3**: "It might even be equivalent to the halting problem." – Rice's Theorem, actually, but same difference.  
  
  ---
  
  