Which of the following recurrence relation is related to worst case time complexity of quick sort ?

Question

Accepted Answer

The correct option is (3):
The recurrence relation for the worst-case time complexity of Quick Sort is $T(n)=T(n-1)+Cn$. The worst-case is triggered when the pivot selection consistently leads to the most unbalanced split possible. This occurs when the pivot always happens to be the smallest or largest element in the sub-array, dividing the problem of size $n$ into a subproblem of size $n-1$ and a trivial subproblem of size 0. The $Cn$ term represents the linear time, $O(n)$, spent on the partitioning operation to place the pivot correctly. Since the problem size only decreases by one element in each recursive step, the depth of the recursion tree becomes $n$, leading to a total time complexity of $O(n^2)$.

The incorrect option is (1):
The recurrence relation $T(n)=T(n/2)+C$ is characteristic of algorithms that operate by reducing the problem size by half in a single recursive call and performing only a constant amount of work, $C$, at each level. The classic example of an algorithm with this time complexity is the Binary Search algorithm. The time complexity of this relation, derived from the Master Theorem or direct substitution, is $O(\log n)$. This complexity is typical of highly efficient search operations, not the time required for a full sorting process, even in its worst performance scenario.

The incorrect option is (2):
The recurrence relation $T(n)=2.T(n/2)+Cn$ models the time complexity for algorithms that divide a problem of size $n$ into two equal subproblems of size $n/2$ and spend $O(n)$ time on the combining or partitioning step. This relation specifically represents the *best-case* and *average-case* time complexity for Quick Sort, where the pivot consistently creates a balanced split. This is also the standard recurrence for the Merge Sort algorithm. Solving this recurrence yields a time complexity of $O(n \log n)$, which is the optimal runtime for comparison-based sorting.

The incorrect option is (4):
The recurrence relation $T(n)=7.T(n/2)+Cn^2$ is not a characteristic model for the Quick Sort algorithm. Quick Sort is a binary recursion, meaning it only generates two subproblems in each step, not seven. While this recurrence can be solved using the Master Theorem (specifically Case 3) to yield a time complexity of $O(n^2)$, which matches Quick Sort's worst-case *order of magnitude*, the structure of the recurrence itself is incorrect for Quick Sort's divide-and-conquer logic.