0
$\begingroup$

Assuming we are observing an algorithm.I am confused as to how one needs to proof correctness.

What exactly the correctness represent for a given algorithm?

And why do we have to proof correctness, in case, correctness itself describes or points out that the algorithm does exactly what we want it to do. Basically the way I understand it, and I am sure I am wrong, proof of correctness, is something like proof of proof???

$\endgroup$
1
  • $\begingroup$ Same difference as between a theorem and a proof. $\endgroup$
    – user16034
    Aug 14, 2022 at 13:30

1 Answer 1

3
$\begingroup$

I claim that this algorithm returns the integer square root of any integer in the range 1 to 1000:

Sqrt(int X)
  return 0

Is it correct ? How can you convince me that it is correct (or incorrect) ?

What about

Sqrt(int X)
  int Y= 1, Z= 0
  while Y != Z:
    Z= Y
    Y= (X / Y + Y) / 2

  return Y
$\endgroup$

Your Answer

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

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