Thanks for your helpful answer What is the asymptotic comple

Thanks for your helpful answer!

What is the asymptotic complexity of the following algorithm? Use big-0 notation where n = the length of the input array AM.

Solution

Answer:

O(n^2) is the complexity .For every element starting from i=1 to n we have to search the array ahead of that element upto last so find minimum element and then swap.

So for first element we have n-1 element so n-1 comaprisons atleast to find the minimum

similarly for i=2(i.e) second element we have n-2 elements ahead so n-2 comparisons atleast

and so on... n-3, n-4.... 3,2,1

Fine?

so total comparisons.... (n-1)+(n-2)+(n-3)+.......+3+2+1

which is sum of first n terms approximately(i.e asymptotically)

which is (n*(n+1)/2)=O(n^2)