I was trying to understand the data structure and different algorithm, but then I got confused to measure the bubble sort time complexity.
for (c = 0; c < ( n - 1 ); c++) {
for (d = 0; d < n - c - 1; d++) {
if (array[d] > array[d+1]) /* For descending order use < */
{
swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}
Now every big O tells the best case O(n), Avg case(n2) and Worst Case(n2). But when I see the code, found in first phase inner loop run n times and then in the second phase n - 1, and n - 2 and so on. That means in every iteration its value goes down. For example, if I have a[] = {4, 2, 9, 5, 3, 6, 11}, so the total number of comparison will be -
1st Phase - 7 time
2nd phase - 6 time
3rd Phase - 5 time
4th Phase - 4 time
5th Phase - 3 time
6th Phase - 2 time
7th Phase - 1 time
so when I calculate the time it looks like = (7 + 6 + 5 + 4 + 3 + 2 + 1) + 7 = 35, but the worst time complexity is n2 as per documentation.
How can I calculate the correct value?
O(n^2)
very much does not mean that the total number of steps will exactly equaln^2
.O(...)
notation. See for example: stackoverflow.com/questions/487258/…