Standard quick sort with the first element as pivot has worst case
AΘ(n log n)
BΘ(log n)
CΘ(n²)
DΘ(n)
Answer & Solution
Correct answer: C. Θ(n²)
When the partition always produces a split of size 1 and n−1 (e.g., the input is already sorted and we pivot on the first element), the recurrence becomes T(n) = T(n−1) + Θ(n) which solves to Θ(n²). This is bubble-sort territory. Best case (balanced splits) is Θ(n log n); the other options are too low.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for