In my algorithms class I have generally been proving algorithms by induction. So for example, given some algorithm $A(n)$ that computes $x$, I show that the algorithm works for some base case, say $A(1)$, then I assume that the algorithm will work for $k<n$. Then I show that the algorithm works for some $z=n$. Are there cases where this won't work or where this isn't recommended? I see algorithms textbooks commonly define loop invariants, and then show that the invariant holds before and after the loop. Is this approach always necessary when dealing with loops? Can't I just assume that it will work for the case where $z=n-1$ and then show it works for $z=n$ i.e. using normal/strong induction?

  • $\begingroup$ If your loops are all simple... $\endgroup$ – gnasher729 Sep 28 '19 at 21:52
  • $\begingroup$ I guess we've just been working through recurrences and easy loops, since direct induction seemed the most intuitive for me to prove correctness. $\endgroup$ – lmeninato Sep 28 '19 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.