Given is the sorting algorithm Bubblesort
Bubblesort(A) for i=1 to A.length for j=A.length downto i+1 if A[j] < A[j-1] swap A[j] with A[j-1]
How do you formally prove that the for-loops will terminate?
Can you just argue that
A.length is finite, thus the outer loop executes finite, namely
A.length times and the inner loop as well just backwards. Thus it's not possible that the inner loop executes more than
A.length^2 times and so both for loops will terminate then.
Can you argue like that? But I don't know how you can prove that without using these sentences, make it more formal. Or is this formal already?