Time complexity

Time complexity of bubble sort

In Bubble Sort, n-1 comparisons will be done in 1st iteration, n-2 in 2nd iteration, n-3 in 3rd iteration and so on. So the total number of comparisons will be

(n-1)+(n-2)+(n-3)…….

sum = n(n-1)/2

= o(n2)

So the time complexity of bubble sort is o(n2).

Time complexity of bubble sort in best case will be o(n).

Time complexity of insertion sort

If we take a closer look at the insertion sort code, we can notice that every iteration of while loop reduces one inversion. The while loop executes only if i > j and arr[i] < arr[j]. Therefore total number of while loop iterations (For all values of i) is same as number of inversions. Therefore overall time complexity of the insertion sort is O(n + f(n)) where f(n) is inversion count. If the inversion count is O(n), then the time complexity of insertion sort in best case is O(n). In worst case, there can be n*(n-1)/2 inversions. The worst case occurs when the array is sorted in reverse order. So the worst case time complexity of insertion sort is O(n2).

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.