Assuming that in a recursive quick sort, each recursive call partitions the inpu
ID: 3639678 • Letter: A
Question
Assuming that in a recursive quick sort, each recursive call partitions the input array into two roughlyequal halves, give the recurrence relation depicting the time complexity; hence, obtain a close form of thetime complexity.
Explanation / Answer
Let T(n) denote the running time of quick sort on an array of size n. Assuming that partitioning creates two subarrays of size n/2, we can write T(n) ˜ 2T(n/2) + cn + d, with constant values c, d attributed to the partitioning operation. For simplicity, we assume that n is a power of 2, that is, n = 2k for some k > 0. Repeated substitution then yields the following. We also use the constant value T(1) = a. T(2k) ˜ 2T(2k-1) + c2k + d ˜ 2(2T(2k-2) + c2k-1 + d) + c2k + d = 22T(2k-2) + 2c × 2k + (2 + 1)d ˜ 22(2T(2k-3) + c2k-2 + d) + 2c × 2k + (2 + 1)d = 23T(2k-3) + 3c2k + (22 + 2 + 1)d · · · ˜ 2kT(1) + kc2k + (2k-1 + 2k-2 + · · · + 22 + 2 + 1)d = a2k + ck2k + (2k - 1)d = ck2k + (a + d)2k - d = cn log2 n + (a + d)n - d. To sum up, T(n) = O(n log n).