AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Easysortingquicksortcomplexity

~60s

Quicksort on sorted input

Quicksort always takes the first element as its pivot. What is its running time on an array that is already sorted in ascending order?

Show the answer and the worked solution

Correct answer: D.

O(n²)

Worked solution

  1. On sorted input the first element is the smallest, so partitioning leaves nothing on the left and n − 1 elements on the right.
  2. The recursion therefore strips off one element at a time and reaches depth n.
  3. The work at each level is proportional to the size still being processed, so the total is n + (n − 1) + … + 1, which is about n²/2 and hence O(n²).

Answer: O(n²).

The idea

Quicksort is fast when partitions are balanced and quadratic when they are not. Choosing a random pivot or the median of three makes the sorted-input worst case vanishingly unlikely.

Shortcut. Sorted input with a first-element pivot is quicksort's textbook worst case: every split is 0 against n − 1, so the recursion is n deep with linear work per level.

Common trap. "O(n log n)" is quicksort's average case, quoted without checking that this pivot rule makes every partition lopsided.

Data Structures & Algorithms

23 of 40

Level

Easy

Target time

~60s

PreviousNext
AI InterviewGet started

Quicksort on sorted input — Aptitude Question

Quicksort on sorted input: Quicksort always takes the first element as its pivot. What is its running time on an… Answer and worked solution on CodeKairo.

Question

Quicksort always takes the first element as its pivot. What is its running time on an array that is already sorted in ascending order?

Options

  1. O(log n)
  2. O(n)
  3. O(n log n)
  4. O(n²)
Show the answer and the worked solution

Correct answer: D. O(n²)

Worked solution

  1. On sorted input the first element is the smallest, so partitioning leaves nothing on the left and n − 1 elements on the right.
  2. The recursion therefore strips off one element at a time and reaches depth n.
  3. The work at each level is proportional to the size still being processed, so the total is n + (n − 1) + … + 1, which is about n²/2 and hence O(n²).

Answer: O(n²).

The idea

Quicksort is fast when partitions are balanced and quadratic when they are not. Choosing a random pivot or the median of three makes the sorted-input worst case vanishingly unlikely.

Shortcut. Sorted input with a first-element pivot is quicksort's textbook worst case: every split is 0 against n − 1, so the recursion is n deep with linear work per level.

Common trap. "O(n log n)" is quicksort's average case, quoted without checking that this pivot rule makes every partition lopsided.

All Data Structures & Algorithms questions · placement mock tests