Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello,

Thanks in advance for answering my questions :)

The question is: What do we mean by "Proving an algorithm"?

I'm having a problem in where to start (if I want to use contradiction for example)...

Thanks again Abdallah

share|improve this question

closed as off topic by Andy Putman, Zev Chonoles, Felipe Voloch, Chris Godsil, quid Feb 12 '12 at 17:25

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
You're asking this in the wrong place. Perhaps math.stackexchange –  Chris Godsil Feb 12 '12 at 17:21
add comment

1 Answer 1

It means to prove

  • that the algorithm terminates
  • that the answer given by the algorithm is correct

It is/seems sometimes obvious, but in general it isn’t.

share|improve this answer
2  
I agree with this answer in the case of more-or-less traditional algorithms, computing some function, which is almost surely what the OP meant. Nevertheless, it might be worthwhile to mention that other notions of proof are appropriate for other sorts of algorithms. For example, if the algorithm uses randomization, you might want to prove reasonable lower bounds for the probability of termination and/or correctness. If the "algorithm" is an operating system, you might want to prove that it doesn't terminate. –  Andreas Blass Feb 12 '12 at 22:56
add comment

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