Normally the running time complexity of a buublesort is O(n^2) but the algorithm given below has a while loop and a for loop the for loop depends upon n but the while loop is simply a checker for a boolean value. Can anyone tell me how would i calculate the running time of this algorithm?
bool done;
done = false;
while ( ! done )
{
done = true;
for ( i = 0 ; i < a.length-1 ; i ++ )
{
if ( a[i] > a[i+1] )
{
// Swap a[i] and a[i+1]
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
done = false;
}
}
}
This case is much harder than the algorithm with two for loops, as the exact number of iterations of the outer loop does not depend just on N, but also on the particular arrangement of the data.
If the array is initially sorted, there will be no swaps at all and the outer loop will run only once, for a complexity O(N).
If the array is initially sorted in reverse, every comparison induces a swap and the outer loop is executed N times for a total complexity of O(N²).
The general case is much more difficult to assess as it depends on the number of outplaced elements. One can show (by a nontrivial mathematical argument) that for an array in random disorder, the average complexity remains O(N²).