10.
MathWorks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
10. (Prog. Concept Question) QuickSort Run Time Complexity
Given a function which finds a median of an array in O(log n). What is the worst case running time for the most efficient algorithm for implementation of quick sort?
Pick ONE option
Show answer & explanation
Answer: B. B) O(n log n)
Finding the exact median splits the array into two equal halves of size n/2, yielding the balanced recurrence T(n) = 2T(n/2) + O(n), which solves to O(n log n).
Step-by-step Derivation:
Step 1: If median is chosen as pivot, the partition is guaranteed to be balanced (n/2 on each side).
Step 2: Recurrence is T(n) = 2T(n/2) + O(n).
Step 3: By Master Theorem, T(n) = O(n log n) even in the worst case.