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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
5
  • 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, 2016 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, 2016 at 18:07
  • $\begingroup$ I suppose I'd go with ​ ​ ​ won't run ​ = ​ will run for 0 time ​ . ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Feb 29, 2016 at 18:11
  • $\begingroup$ @templatetypedef I will post the code as you say. $\endgroup$
    – Anish
    Feb 29, 2016 at 18:17
  • 2
    $\begingroup$ @anish7 The claim that the questions were correct may itself have been incorrect! $\endgroup$
    – David Richerby
    Feb 29, 2016 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.

Improve this answer
$\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.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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