[Solved]: Calculating time complexity of a code which may be incorrect

Problem Detail: 

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.

Asked By : anish7

Answered By : templatetypedef

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53801