Skip to content
Q15Section DA (Data Science and Artificial Intelligence (Q11–Q65))15 of 65

Expected-time recurrence for quicksort with random pivot position

Consider that the quick sort algorithm is used to sort an array of nn distinct randomly ordered elements. In every call, the pivot is chosen as the first element of the current subarray. Let T(n)T(n) denote the expected time to sort the array. Assume that the time to partition is linear in the size of the current subarray. Which of the following recurrence relations correctly represents T(n)T(n) in this scenario?

Options

Pick an option to check your answer. In a mock test a wrong answer here costs 1/3 mark.