Question

Calculate the time complexity of each algorithm for best, worst and average cases. Give all steps of your calculation and results in Big-O notation.

algorithm :
Selection Sort

Bubble Sort

Insertion Sort

Answer 1

* N is the length og the array which we want to sort

Selection Sort

Selection sort divides the list into two parts - sorted and unsorted. And on every turn finds the min element from the unsorted list and put it in sorted list.
This operation continues till the unsorted list contains 0 elements.

It is independent of the elements as it will always do a full scan of the unsorted list to find the min element.

Thus, the best, worst and average complexity of this algorithm is O(NlogN)

Bubble Sort

In Bubble sort, adjacent elements are compared and depending on their values their values are swapped. This process continues till last and second last element. Once it reaches end of the array, it starts again from the start and try to do the same thing.

It is again independent of the element order, since it always compares adjacent elements.

Thus, the best, worst and average complexity of this algorithm is O(NlogN)

Insertion Sort

In insertion sort, the list is divided into two parts, sorted and unsorted. Elements are first compared with the last element of sorted list. If the element is smaller than last element, they swap. This process continues till we reach to the first element of the sorted list. By the end of this iteration or process, all the elements in first list are sorted and then we move with the same process with next element in the unsorted list.

It is independent of the order of elements since we will be compareing elements always.

Thus, the best, worst and average complexity of this algorithm is O(NlogN)