Made Easy Test Series 2024

Question

Which of the following statement(s) is/are true?

(a) Quicksort and merge sort are both examples of divide and conquer algorithms.

(b) If we randomly choose a pivot element each time, quicksort will always terminate in time $O(n log n).$

(c) For every fixed strategy to choose a pivot for quicksort, we can construct a worst case input that requires time $O(n)$.

(d) If we could find the median in time $O(1)$, quicksort would have worst case complexity $O(n log n)$.

plese give answer and explain it why ?

Comments

@jugnu1337 for option B), they have used randomized quicksort and there are chances for getting time complexity of O(n^2) although the chances are somewhat else than normal quicksort

---

@BhargavPatel. i think. will always terminate   make this statement wrong,

---

@jugnu1337 lets assume the case where we randomly selecting smallest or lagest element so that here $T(n)= n^2$

Answer 1

Option A) Both $Quick Sort $ and $MergeSort$  are both examples of divide and conquer.In $MergeSort$ we do blind division and try to conquer on the small sub problems while in $QuickSort$ we perform meaning division so we don’t bear the conquer cost.

Option B)If we randomly choose a pivot the quick sort will not end up giving $\Theta$(nlogn) Time complexity in every case but less no of groups will the worst case of $\Theta$(n$^{2}$). for sure.

Option C)Every partition technique takes $O(n)$ to choose the pivot whether its Hoare or Lomuto
Analysis of Hoare vs Lomuto:https://en.wikipedia.org/wiki/Quicksort 

Option D)Given that we can find the median in 0(1) we can always simulate $QuickSort$ to perform in $\Theta$(nlogn) but generally the median finding takes more time and $Merge Sort$ out performs the constant factor that gets added for $median$ using the median of medians finding and then applying the $QuickSort$.

Correct answers will be option $A)$,$C)$and $D)$

Comments

@Psy Duck Correct answer is ACD , you have to edit your answer in Option C they are saying that time complexity of constructing input is $O(n)$ not the comlexity of quick sort.

---

@Ray Tomlinson edited .I misread the option :)