What is the worst-case time complexity of the standard QuickSort algorithm when the chosen pivot is consistently the smallest or largest element?
Answer and explanation
Correct answer: D. O(n²)
- Step 1: Analyze QuickSort partition efficiency with poor pivot selection.
- Step 2: When the pivot is the extreme element at every step, the partition is maximally unbalanced (size and ). The recurrence relation becomes , summing to .
Answer
O(n²).
Why not the others: is the average and best-case complexity; is tree height; is exponential complexity.
Practise more Algorithms and Python Programming.
Free questions with an explanation for every one, and full timed EmSAT Achieve (UAE) mock tests.
More Algorithms and Python Programming questions
- What is the output of the following Python expression: [x**2 for x in range(6) if x % 2 != 0]?
- What is the worst-case time complexity of searching for an element in a balanced binary search tree (AVL tree) containing n nodes?
- What will be printed by the following Python code snippet?
def func(val, lst=[]):
lst.append(val)
return lst
print(func(1))
print(… - Which abstract data structure operates on a First-In, First-Out (FIFO) ordering principle?
- What is the return value of executing the recursive Python function `mystery(4)`?
def mystery(n):
if n <= 1:
return 1
retur… - In Python, which of the following built-in data types is immutable?