I am studying algortithm design and I was looking for help in the proof excercises. Considering the below algorithm

Sort1(A[1, 2, . . . , n])
 for i = 1, 2, . . . , n do
   for j = 1, 2, . . . , n −1 do
     if A[j] > A[j   1] then
        swap A[j] and A[j   1]
     end if
    end for
 end for

I need to come up with a base case and inductive proof of correctness for this algortihm.

I attempted the base case and it looked something like this

Base Case : For n = 1, T(n) <= C = C.n^2
Assuming T(n/2)  <=  c.n^2
 = 2T(n/2)   Cn
 = 2Cn^2   Cn
 = 2Cn(n 1)

I am not really sure of this correctness , so i would really appreciate if someone could review and suggest me the right path. Thanks in advance..

CodePudding user response：

Base Case

A base case proof of correctness would start with a simple example of the array such as the empty case, or the case where there is only one item.

So you would prove, for example, that the algorithm sorts correctly for the case of N=0.

Inductive Hypothesis

The the next step would be to assume the algorithm is correct for the case of N=K. You would then show that based on N=K being correct, you can take as step in the algorithm and guarantee that it will be correct for N=K 1.

Proving

Actually doing that is the hard, part and sometimes could involve proving that given that the previous K elements were sorted, you can guarantee that array will be sorted with K 1 elements.

Alternatively you can assume by contradiction that while it is sorted for K elements, that adding another element could cause the K 1 case to not be sorted, and then demonstrate some contradiction. Thus proving that the K 1 case is valid.

In this example

In this case you'd want to focus on how conditionally swapping the last element with all the previous ones will guarantee that it will fall in the correct place assuming all the previous K elements are already in the right place (which is the inductive hypothesis).