Complexity of sorting techniques

[himanjim]

Hi,
I' studying various sorting techniques...And one thing I'm not clear about the complexity of the techniques...
For e.g the complexity of bubble sort is
Average Case=>O(n*n)
Worst Case=>O(n*n)
Best Case=>O(n*n)
Obviously n is the no. of elements in the array...
But even in the worst case i.e the array having 5 elements in descending order would do only only 4+3+2+1 comparisons
and not O(n*n) which I expect is 5*5=25 comparisons
Can somebody please throw light on it??

[sj87]

May be it helps you to see a little math ( cause, math doesn't lie ;-) ):

The pseudo-code for this algorithm has this structure:

FOR I = 0 TO N-1 /* It cuts when it compares against N */
      FOR J = 0 TO N-I-1 /* It cuts when it compares against N-I */
            IF ( VEC[j] > VEC[j+1] )
                   SWAP /*...bla bla...*/

So as you can see, in the worst case...

For I = 0 ---> J = 0 TO N-1 ----> 2*(N-1) + 1 comparisons. N-1 From the internal loop ( you can't forget about the condition that its checked every time you re-enter the loop ). But in each entry of the internal loop you have another comparison made by the IF, so we have 2*(N-1). The last comparison that we add is the cut of the loop, meaning the last comparison where J = N-1.
If you follow the same way of reasoning, you will get to this:

When I = N-1 ( end of external loop ) ---> J = 0 TO N - ( N-1+1 ) = 0 So comparisons at this point are 2*0 + 1 = 1. So as you can see the final amount of comparisons is:

N From the external loop ( counting "cut comparison" )and

2*\sum_i^{N-1} i = 2*\frac{(N-1)*N}{2}

for the internal loop. Besides, you have N-1 "Cut comparisons". So...

C(N) = N + 2*\frac{N^2 - N}{2} + N = N^2 + N

And Big O for this algorithm results in...

O(N^2)

Good Luck!

[SRaj]

Reply: hello friend abt your question , what you know the worst case of bubble sort is (n*n) but in loop we write a condition that the loop must not got till nth (n-i-1) where i is always incrementing. That is why every time n's value is decreasing (if you know how recursive algorithm works eg. in factorial value) so if n=5 then next time it will be 4 and so bcoz of increament of i so the solution will be (4+3+2+1) ("In first loop itself it compares till n-1 which is 5-1=4") =10.
I think you might have got the idea.
ok take care bye

[ArkM]

For e.g the complexity of bubble sort is
Average Case=>O(n*n)
Worst Case=>O(n*n)
Best Case=>O(n*n)

Apropos, the best case compexity of bubble sort with swapped flag improvement is O(n) - it stops after the 1st pass;)

[Freaky_Chris]

Either way very very old thread, don't drag anymore up SRaj

Chris