SESKStuff Everyone Should Know
SESK: Stuff Everyone Should Know · sesk.info/tech-insertion-sort-quadratic

What is the worst-case running time of insertion sort on n items?

O(n²), quadratic: double the items, about four times the work.

Start playing free

  1. O(n log n)
  2. O(n²) ✔
  3. O(log n)

Why: Insertion sort takes each new item and slides it back past every bigger item already sorted. In a reverse-sorted list, item number k moves k places, and adding those up gives about n squared over 2 moves.

Huh, didn't know that: On reverse-sorted input, each new item can move past every item before it.

The dad joke
Insertion sort is how I organize cards in my hand. Slowly, and with a lot of shuffling.
Like this card?
Play the game

References

Answer: O(n²). Insertion sort takes each new item and slides it back past every bigger item already sorted. In a reverse-sorted list, item number k moves k places, and adding those up gives about n squared over 2 moves.

  1. MIT 6.006 Introduction to Algorithms, Lecture 3: Sorting ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec3
    insertion sort analysis: ... T(1) = Θ(1), T(n) = T(n − 1) + Θ(n) =⇒ T(n) = Θ(n2)
    Checked 2026-10-10.

Think this answer is wrong? Tap "Challenge this answer" on the card in the game and tell us why.

Test yourself in the game

Tech & GadgetsHow fast is binary search on a sorted array of n items, in Big O terms?Tech & GadgetsWhat must be true about a list before you can use binary search on it?Tech & GadgetsIn Big O notation, what do you ignore when describing an algorithm's running time?

That's stuff everyone should know.