Time taken by quick sort algorithm is
Optym technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Time taken by quick sort algorithm is
Show answer & explanation
Answer: B. B) T(n) = T(k) + T(n-k-1) + θ(n)
Quick sort partitions the array of size n around a pivot into subarrays of size k and n-k-1 with Theta(n) partitioning work, yielding T(n) = T(k) + T(n-k-1) + Theta(n).
Step-by-step Derivation:
Step 1: Partitioning an array of n elements takes linear time Theta(n).
Step 2: If the pivot ends at rank k, the left subarray has size k and the right subarray has size n - k - 1.
Step 3: The recurrence is T(n) = T(k) + T(n-k-1) + Theta(n).