In quick sort, for sorting n elements, the (n/4)th smallest element is…
2009
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as a pivot using an O(n) time algorithm. What is the worst-case time complexity of the quick sort?
Answer: B. θ(nlogn) — Answer: θ(n log n) Reasoning: Selecting the (n/4)th smallest element as the pivot guarantees that the pivot splits the array into two parts of size at most…
- A.
θ(n)
- B.
θ(nlogn)
- C.
θ(n2)
- D.
θ(n2 log n)
Attempted by 387 students.
Show answer & explanation
Correct answer: B
Answer: θ(n log n)
Reasoning: Selecting the (n/4)th smallest element as the pivot guarantees that the pivot splits the array into two parts of size at most 3n/4 and at least about n/4.
Recurrence: T(n) = T(n/4) + T(3n/4) + Θ(n)
Each level of recursion does Θ(n) work for partitioning and the linear-time selection.
The largest subproblem size shrinks by a constant factor (at most 3/4) each level, so the number of levels is Θ(log n).
Combining these gives total time Θ(n) per level × Θ(log n) levels = Θ(n log n).
Explore the full course: Iocl Engineers Officers Grade A Paper 2