2
$\begingroup$

I am a sophomore taking a course in algorithm analysis. We were asked by our professor to calculate time-complexity of several C functions, but some of them were incorrect and would result in a compile error. As far as I know time complexities of correct algorithms are calculated and then we choose which one to implement. We tried to discuss this with her but she insisted on solving those problems nevertheless stating that it doesn't matter whether the code gets executed or not.

Is there a way one can realise that the algorithm is incorrect after finding it's time complexity?

Does it make sense calculating time complexity for an incorrect program?

PS :

1) The program wasn't implementing any proven algorithms, it was just some loops.

2) This may sound like a silly question, but my professor got me confused.

Downvotes are welcome but please give your opinion.

$\endgroup$
3
$\begingroup$

On a more practical level, it sounds like this probably just stems from a typo on the instructor's part. If this is in the context of a big-O exercise, I'd just fix the typos and move on. Instructors do make mistakes too!

Getting a bit more abstract, if a program won't run, it doesn't really make sense to speak of its time complexity because it has no runtime.

Getting even more abstract - you actually can use big-O analyses to show that certain pieces of code cannot be correct. For example, suppose someone proposes a new comparison-based sorting algorithm. If you do a big-O analysis and see that it runs in time O(n) in the worst case, you are guaranteed that the code has to be wrong because of the requirement that all comparison-based sorting algorithms run in time $\Omega(n \log n)$ on average. This is different than talking about code that won't even compile, but it does show that analyzing the time complexity of incorrect (here, legal but wrong) code may be worthwhile.

$\endgroup$
  • 2
    $\begingroup$ Yes, instructors do make mistakes but we were asked that question in a test. We were told that all questions in the paper are correct. Thanks for the answer. $\endgroup$ – Anish Feb 29 '16 at 17:50
  • 1
    $\begingroup$ @anish7 As someone who has taught courses and has made minor typos on exams, it's not all that unheard of for that to happen. As long as you're not breaking any policies by doing so, you may want to consider posting the code in a separate question and confirming that it is indeed a typo. That might be a good fit for Stack Overflow. $\endgroup$ – templatetypedef Feb 29 '16 at 18:07
  • $\begingroup$ I suppose I'd go with ​ ​ ​ won't run ​ = ​ will run for 0 time ​ . ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Feb 29 '16 at 18:11
  • $\begingroup$ @templatetypedef I will post the code as you say. $\endgroup$ – Anish Feb 29 '16 at 18:17
  • 2
    $\begingroup$ @anish7 The claim that the questions were correct may itself have been incorrect! $\endgroup$ – David Richerby Feb 29 '16 at 18:32
1
$\begingroup$

Not obviously - if complexity is below the lower bound - it is probably wrong (e.g. summing N elements require to read N, cannot get lower), but N^2 tells this is not optimal, but this is unknown from that stat whether it works in fact.
If there are simple loops - you can calculate complexity without executing it.
Wall time may be misleading and takes into account resources, cache and other factors.
Simple mistakes in the code like "foor" instead of "for" prevents it from compiling - but if you can correct such mistakes - it changes nothing in complexity.
If code is damaged beyond repeair - it cannot be calculated at all.

Because this is excersise to calculate complexity - yes it makes sense.
If you were given pseudocode - it also does not compile, but still you can calculate it.

$\endgroup$
1
$\begingroup$

Correctness is relative -- with respect to what specification¹?

Technically, C code is never run; it is always compiled to some machine code. So, if you want to be really nitpicky, it is impossible to properly analyse the runtime cost of C code. You'd need to be told which compiler and machine will be used for executing it.

That said, we usually want to analyse the represented algorithm with respect to some abstract cost measure instead. That makes a difference because now there is some tolerance for simple syntax errors. As long as it is clear what algorithm we talk about, analyze away. In fact, most sources use more or less well-defined pseudocode instead of real code.


  1. If the code compiles and does not do what you want it to, it still has meaningful runtime costs.
$\endgroup$

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.