CODEWITHSUNDEEP
algorithmsortingbig-otime-complexitycomplexity-theory
user3739406
user3739406

Reputation: 364

Analyzing Simple Bubble Sort Loop (Worst Case)

I'm given a simple pseoducode algorithm:

for j=1 to A.length-1 //first line 
  for i =1 to A.length-j //second line 
    if A[i-1] >A[i]
      swap A[i-1] and A[i]

I'm told that the second line runs as such (WORST CASE:

n+(n-1)+...+2 = n(n+1)/2-1

I understand that when the first line runs, the second loop runs n times, each next iteration of j, the second loop runs 1 less times (n-1) +(n-2) etc. I understand that it's clearly a summation, here but what I don't get is why the last thing added is 2 (FOR THE SECOND LINE).

Any input would be much appreciated.

Upvotes: 1

Views: 116

Answers (1)

Am_I_Helpful
Am_I_Helpful

Reputation: 19158

Considering A.length to be n, you could clearly verify the same. I am doing it for you :

for j=1 to n-1 //first line 
  for i =1 to n-j //second line 
    if A[i-1] >A[i]
     swap A[i-1] and A[i]

So, for the first iteration of outer loop at j = 1, inner loop runs from 1 to n-1 times. => n-1

For second iteration of outer loop, inner loop runs from 1 to n-2 times. => n-2

For ith iteration of outer loop, the inner loop will run for 1 to n-i times, => n-i .

Last iteration of outer loop will be when j = n-1, the inner loop will run for i = 1 to n-(n - 1) = 1 time.

So, result will be summation of n-1 + n-2 + ... + 1 = (n-1)*n/2.

SO, it should be obviously 1 at the end.

I understand that it's clearly a summation, here but what I don't get is why the last thing added is 2 (FOR THE SECOND LINE).

I suggest you to talk with your friend/professor over this, who has, obviously, incorrectly informed you. It is what I have solved here.

People generally think that when the array's top n-1 elements have been sorted, the last one would already fit the exact place. So, they generally presume this and leave the last step.

But, in computation OR algorithm, we (generally) compute this. Your this code is computing that here.

Upvotes: 3

Related Questions