How to compute total correctness of an algorithm by induction

Overview

Mathematical induction is used to prove the total correctnessAn algorithm is totally correct if it receives valid input, gets terminated, and always returns the correct output. of an algorithm. It's mostly used for recursive algorithms.

Proof by induction includes three steps:

1. Prove base case
2. Assume true for an arbitrary value of $n$ (Also known as the induction step)
3. Prove true for the case $n +1$

This may help us understand induction:

Suppose you have millions of dominos, spaced out perfectly. How will we know that every domino will fall when we tip the first one?

We don't have to check every single domino. We only have to prove the following:

• The first domino will fall perfectly.
• After tipping the first domino, every other domino will tip the next domino over.
• With these two things, we can prove that a million dominoes will fall.

Example

Let's understand this through an example of proving an algorithm that calculates the factorialProduct of that number with all the numbers less than it, down to 1. of a positive integer:

Base case

This is the first step of the proof. Here, we try to verify that the algorithm holds for the first number from a valid range of inputs.

As the factorial function will work on all positive integers, then the base case would be when $n = 1$.

Induction step

In this step, we prove that if the algorithm is working for any arbitrary value of $n$, it will also work for $n + 1$.

Assumption: For the program, after going through$n$times, it should return $n!$.

After our assumption, we'll try to prove that it also works on $n + 1$. This means after going through $n + 1$ times, the algorithm will return $(n + 1)!$ . For this try to dry run $fact(n+1)$, we already forwarded through $n$iterations.

• After $n$iterations $fact()$ returns $n!$.
• At $n+1$iterations $fact()$returns $n* (n - 1)!$.
• When $fact()$approaches base step it terminates the program.

The loop variant works because the $fact()$returns $n *(n-1)!$, which are equivalent to $(n+1)!$.

Conclusion

The loop stops after$n$ iterations, and the algorithm returns the required output that is $n!$and terminates as well. Therefore, our algorithm is correct.