Suppose I have an array of descending Numbers(Worst Case scenario) Like:
Nums = {50,40,30,20,10} (size = 5)
Now If I use Selection sort (which would sort them in ascending):
Selection Sort Algorithm:
for(i=0; i<=size-2; i++)
{
for(j=i+1; j<=size-1; j++)
{
if(Nums[i]>Nums[j])
{
temp=Nums[i];
Nums[i]=Nums[j];
Nums[j]=temp;
}
}
}
Now If we analyse the Number of Operations or Iterations performed, Here is how the indexes are compared
(OuterLoopIndex Vs InnerLoopIndex):
1st Iteration: 0 - 1, 0 - 2, 0 - 3, 0 - 4
2nd Iteration: 1 - 2, 1 - 3, 1 - 4
3rd Iteration: 2 - 3, 2 - 4
4th Iteration: 3 - 4
Now If add all the total number of operations in each iteration they are exactly
10 (4 + 3 + 2 + 1) Which is Like Sum of N numbers whose formula is N(N+1)/2 (basic math) but in our example here N is not the size its the last index of array which would be size-1 so here N would be N-1.
Hence we would get something like this if substitute N=N-1 in N(N+1)/2
=> (N-1)(N-1+1)/2
=> N(N-1)/2
Same goes for Bubble and Insertion sort. So why efficiency of those sorting algorithms is said to be be n^2 and note n(n-1)/2 ?
when size=5 we would get 25 if we consider n^2, but only 10 when considering n(n-1)/2 ? Why/How n^2 is still considered as efficiency here ?
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…