Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
456 views
in Technique[技术] by (71.8m points)

algorithm - Why efficiency of selection sort or Bubble or Insertion sort is said to be n^2 and not as n(n-1)/2

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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

In big-O notation only the most significant term counts, and constant coefficients are ignored:

O[n(n-1)/2] = O[n2/2 + n/2] = O[n2/2] = O(n2)

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...