---
title: "Efficiency of quick sort"
subject: "Data Structure and Algorithm"
chapter: 7
key: "semester_4/data_structure_and_algorithm:quick-sort-efficiency"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/quick-sort-efficiency
site: BCT Engineering
---

# Efficiency of quick sort

Data Structure and Algorithm · Chapter 7: Sorting

- Asked in: 2069 Poush, 3 marks; 2068 Magh, 2 marks (asked 2 times)
- Video: [Analysis of Quick Sort Algorithm | Time complexity of Quick Sort Algorithm | O(n^2) | O(n log n)](https://www.youtube.com/watch?v=YQhfIoK8UDY) — CS Talks by Lee!
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/quick-sort-efficiency
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7

## Question

Show that efficiency of quick sort is O(n log(n)). (Calculate the efficiency of quick sort.)

## Short answer

Quick sort divides using a pivot. Best/average case T(n)=2T(n/2)+cn solves to O(n log n). The worst case with an already sorted array is O(n²). Random or median-of-three pivot makes O(n log n) typical.

## Answer

Quick sort picks a pivot, partitions the array so that smaller elements are on its left and larger ones on its right, then sorts both parts recursively. Partitioning n elements takes n − 1 comparisons, i.e. O(n).

Let T(n) be the time to sort n elements and let the pivot end at position k.

T(n) = T(k) + T(n − k − 1) + cn

#### Best case (pivot splits the array in the middle)
T(n) = 2T(n/2) + cn

Expanding: T(n) = 2[2T(n/4) + cn/2] + cn = 4T(n/4) + 2cn = ... = 2ʲ T(n/2ʲ) + j·cn.

The recursion stops when n/2ʲ = 1, i.e. j = log₂ n, so T(n) = n·T(1) + cn·log₂ n = **O(n log n)**.

Another view: there are log₂ n levels of recursion and each level does about n comparisons in total, giving n log₂ n.

#### Average case
For random data the pivot lands at every position with equal probability: T(n) = (1/n) Σₖ [T(k) + T(n−k−1)] + cn, whose solution is about 1.39·n·log₂ n, still **O(n log n)**.

#### Worst case
The array is already sorted (first element as pivot): one part is empty and the other has n − 1 elements, so T(n) = T(n−1) + cn = c(n + (n−1) + ... + 1) = cn(n+1)/2 = **O(n²)**.

| Case | Complexity |
|---|---|
| Best | O(n log n) |
| Average | O(n log n) |
| Worst | O(n²) |

Choosing the median-of-three or a random pivot makes the worst case very unlikely. Extra space is O(log n) for the recursion stack.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How many comparisons does partitioning n elements take in quick sort?
   A. n^2
   B. n - 1, i.e. O(n)
   C. log n
   D. n log n
   Answer: B. Each element is compared with the pivot once, so partitioning is O(n). (Key point: Partition cost)

2. Why is the best case of quick sort O(n log n)?
   A. The pivot always ends at the first position
   B. The array is already sorted
   C. The pivot splits the array in the middle, giving log2 n levels each doing about n work
   D. Partitioning takes constant time
   Answer: C. A middle split gives T(n) = 2T(n/2) + cn, i.e. log2 n levels with about n comparisons per level. (Key point: Best case)

3. When does quick sort reach O(n^2) with the first element as pivot?
   A. Random data
   B. When the array is already sorted, so one part is empty and the other has n - 1 elements
   C. When n is a power of 2
   D. When all splits are in the middle
   Answer: B. T(n) = T(n-1) + cn sums to cn(n+1)/2, which is O(n^2). (Key point: Worst case)

## Related in Data Structure and Algorithm

- [Efficiency of straight selection sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aselection-sort-efficiency) — Data Structure and Algorithm, chapter 7

## Related in other subjects

- [Jet on flat plate, force and efficiency](https://www.bctengineer.com/question.md?key=semester_3%2Ffluid_mechanics%3Ajet-on-flat-plate-efficiency) — Fluid Mechanics, chapter 7
- [Trickle charging and Ah/Wh efficiency (4 A, 12 h, 1.2 V)](https://www.bctengineer.com/question.md?key=semester_6%2Findustrial_power_distribution_and_illumination%3Atrickle-charging-4a-1-2v) — Industrial Power Distribution and Illumination, chapter 9, asked 3×
- [Trickle charging and Ah/Wh efficiency (2.2 V, 2.44 V)](https://www.bctengineer.com/question.md?key=semester_6%2Findustrial_power_distribution_and_illumination%3Atrickle-charging-2-2v) — Industrial Power Distribution and Illumination, chapter 9, asked 3×
- [Battery charger bridge 15 V: currents, power, efficiency](https://www.bctengineer.com/question.md?key=semester_7%2Fpower_electronics%3Abattery-bridge-15v-efficiency) — Power Electronics, chapter 2, asked 3×