A) what is the time complexity for selection sort to sort a list of n elements B

Question

A) what is the time complexity for selection sort to sort a list of n elements B) what is the time complexity for merge sort to sort a list of n elements C)what is the time complexity for quick sort to sort a list of n elements A) what is the time complexity for selection sort to sort a list of n elements B) what is the time complexity for merge sort to sort a list of n elements C)what is the time complexity for quick sort to sort a list of n elements B) what is the time complexity for merge sort to sort a list of n elements C)what is the time complexity for quick sort to sort a list of n elements

Explanation / Answer

A) Selection sort :

In selection sort, there are n-1 iterations:

in first iteration, first element will be compared to all other n-1 elements and minimum element will be found and then it will be swapped with first element at the end of first iterations.

in second iteration, minimum element from remaining n-2 elements will be found out and then it will be swapped with second element.

similary for 3rd, 4th .. upto n-1 iterations.

here , in first iterations there are n-1 comparisions, in second iteration there are n-2 , in third n-3.. and so on.

so total number of comparisions can be given as sum of first n-1 numbers.

hence worst time complexity for selection sort is O(n2) to sort list of n elements.

B) Merge sort :

In merge sort, divide and conquer approach is used.

The list of n element is divided into two list of n/2 elements, each list of n/2 elements will further gets divided into list of n/4 elements.

Division keeps occuring until the resulting list remains with 2 elements only.

Then sort those two elements in each sub list.

Then keep merging smaller lists.

This results in sorted list of n elements.

Here, dividing into smaller lists takes log2n time and meriging takes O(n) time.

So total time required to sort list of n elements can be shown as O(n log2n).

C) Quick sort :

Quick sort also uses divide and conquer algorithm.

In quick sort, there are n-1 iterations and at each iterations, one pivot element is selected and all elements that are less than pivot are positioned on left side of pivot and all elements that are bigger than pivot are positioned on right side of pivot.

At each iteration, one element's position into sorted list is decided and problem further gets divided into two sub problems, one is element that are at left side of the list and another is elements that are right side of the list.

Here in worst case, selected pivot element can be left most or right most element of the sorted list.

so in worst case scenario, complexity of Quick sort is O(n2) .

With proper selection of pivot it can be happen in O(n log n) time too.

if you have any doubts, you can ask in comment section.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.