Question

compare the time efficiency of the insertion sort algorithm with the bubble sort algorithm. Give the big theta notation of each of the algorithms as a part of your answer.

Answer 1

Insertion Sort:-

It is a simple sorting technique that is similar to sorting playing cards. It virtually divides the array into two parts- sorted and unsorted part.

Values in the sorted part of the array are picked one by one and are placed in their proper positions.

Bubble Sort:-

Bubble sort is a simple sorting method that repeatedly compares two adjacent elements and swaps if they are in the wrong order.

The time complexity of both algorithms is the same in all cases.

The best-case complexity of both algorithms is Theta(n), this is when input is a sorted array in both algorithms.

The worst-case complexity of both algorithms is Theta(), this is when input is a reversed sorted array, or very less elements of the array are in position.

The average-case complexity of both algorithms is Theta().

Note:- Please comment down if you face any problem. :)