Time complexity

Question

Which of the following sorting algorithm has almost the same worst case and best case complexity?

1- Quick Sort

2- Merge Sort

3- Shell Sort

4- Heap Sort

 

PS:  Is it heap or shell, I am confused. Please clarify me.

Comments

refer this http://bigocheatsheet.com/

i think merge will be the answer

---

it will be either Merge or Heap sort because both have $O(n\log n)$ complexity

Shell sort best case -> $O(n\log n)$, Worst Case-> $O(n^{2})$

---

Both Heap and Merge Sort have same Time Complexity in Worst as well as Best Case is Equal To  : O(nlogn)

Answer 1

Sorting algorithms are important concepts and should be understood properly :-

1. Quick sort :- Everything is about the selection of pivot. If we choose pivot randomly and say i selected a pivot which is the greatest or least element, and following that if I partition the array then:

T (n) = T (n-1) + n  = O(n^2)

Else if pivot is not the greatest or smallest then it's equivalent to:-

T(n) = 2T (n/2) + n = O (nlogn)

2.In case of merge sort it doest depend on pivot sort of thing hence it's not a liability here it is based on dividing the array and sorting these small arrays and combining them :-

T (n) = 2T (n/2) + n = O (nlogn)

3. Shell sort what to say it's nearly like insertion sort.

Shell sort best case -> O(nlog⁡n), Worst Case-> O(n^2)

4. Heap sort :- it's based on a complete binary tree whose height is logn. Hence for creating heap = O (n) and after that we delete the root (heap means min heap) we get 1st smallest element it takes O (logn) per delete operation. Hence for n delete operation: - O (nlogn) which is it's best and worst case.

Comments

So answer is heap sort?

---

As per the question both merge sort and heap sort has O(nlogn) time so both are answers

---

Explanation is right. So answer should be both merge or heap .

---

Thank you