S4 16 16 Find the average case complexity of the Exchange S

S4 #16 )

16. Find the average case complexity of the Exchange Sort algorithm for sorting 3 distinct elements (n-3) for each of the following operations of assignments of keys and of comparisons. Exchange-Sort (A, n Sorts the Array A(1:n in non-decreasing order. for i 1 to n do for j i 1 to n do exchange (A0, A( endif endfor endfor

Solution

Average case complexity of above code depends on loops.In following code there are two loops.average complexity depends on innermost loops.so complexity is O(n^2)