Proof of the Bubblesort algorithm
Your induction hypothesis is insufficient. In the hypothesis, you are just proving that the last element of the array has the maximum value. However, you have to prove that the resulting array is sorted. Therefore, your induction hypothesis should be the following:
Hypothesis: At the end of 't' iterations of the outer &quot;for&quot; loop, the &quot;n-t&quot; highest elements of the array are in the sorted order and they occupy the indexes from 'n-t+1' to 'n'.
Base case: For 't = 1', the induction hypothesis says that at the end of the first iteration of the outer &quot;for&quot; loop, the algorithm gives the highest element at the index 'n'. And, you can easily prove this statement.
Induction Step: At the end of 't+1' iterations of the outer &quot;for&quot; loop, the &quot;n-t+1&quot; highest elements of the array are in the sorted order and they occupy the indexes from 'n-t' to 'n'. Again, you have to prove this step using the earlier mentioned hypothesis -- for 't' iterations.
This proves the induction hypothesis. And, now you can simply say that at the end of 'n' iterations of the outer &quot;for&quot; loop, all elements of the array are in the sorted order and they occupy the indexes from '1' to 'n'.