Complexity

[Progesco]

Please help me to answer this question. Why complexity of bubble sort is O(n²) and quicksort is O(nlog₂n)? and what about complexity of cocktail shaker sort?

Thank you

[jsmith]

Complexity of sorting algorithms is always defined by the number of comparisons that are required.

The bubble sort algorithm is:


for( i = elements 1 through N - 1 )
for( j = elements 1 through N - i )
if( element[ i ] > element[ j ] )
swap( element[ i ], element[ j ]);


How many times does the if() execute?

The outer for loop executes N - 1 times.

The inner for loop executes N - i times, which means that
on the first time through the loop, it executes N - 1 times, the
second time N - 2, and so forth, down to N - ( N - 1 ) = 1.

So N - 1 + N - 2 + N - 3 + ... 1, as you know from math, is
the sum of all integers 1 to N - 1. The sum of all integers
1 to k has the formula k * ( k + 1 ) / 2. If we let k = N - 1, then
we have the formula (N - 1) * N / 2 == ( N^2 - N ) / 2.

We know from Big-O notation that N^2 dominates N, so
the algorithm is O( (1/2)N^2 ). But we know also that
O( kN^2 ) where k is constant (in this case 1/2) is equal
to O( N^2 ).

Now you can look at the other sorting algorithms are
perform the same logic.


So in other words,