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

~60s

Best case of insertion sort

What is the best-case running time of insertion sort, and on which input does it occur?

Show the answer and the worked solution

Correct answer: B.

O(n) on an already sorted array

Worked solution

  1. Insertion sort takes each element and shifts it left past the larger elements already placed.
  2. On sorted input the very first comparison of each pass fails and no shifting happens at all.
  3. That is one comparison per element, n − 1 in total, so the best case is O(n) on an already sorted array.

Answer: O(n) on an already sorted array.

The idea

Best, average and worst case all describe inputs of the same size n. Insertion sort's linear best case makes it the standard finishing pass inside hybrid sorts such as introsort and Timsort.

Shortcut. Best case is stated for a general n, which rules out the single-element O(1); on sorted input each element costs one failed comparison, so O(n).

Common trap. "O(1) on a single-element array" is the fastest possible run, but best case is defined for inputs of arbitrary size n.

Data Structures & Algorithms

27 of 40

Level

Easy

Target time

~60s

PreviousNext
AI InterviewGet started

Best case of insertion sort — Aptitude Question

Best case of insertion sort: What is the best-case running time of insertion sort, and on which input does it occur? Answer and worked solution on CodeKairo.

Question

What is the best-case running time of insertion sort, and on which input does it occur?

Options

  1. O(1) on a single-element array
  2. O(n) on an already sorted array
  3. O(n log n) on a randomly shuffled array
  4. O(n²) on a reverse-sorted array
Show the answer and the worked solution

Correct answer: B. O(n) on an already sorted array

Worked solution

  1. Insertion sort takes each element and shifts it left past the larger elements already placed.
  2. On sorted input the very first comparison of each pass fails and no shifting happens at all.
  3. That is one comparison per element, n − 1 in total, so the best case is O(n) on an already sorted array.

Answer: O(n) on an already sorted array.

The idea

Best, average and worst case all describe inputs of the same size n. Insertion sort's linear best case makes it the standard finishing pass inside hybrid sorts such as introsort and Timsort.

Shortcut. Best case is stated for a general n, which rules out the single-element O(1); on sorted input each element costs one failed comparison, so O(n).

Common trap. "O(1) on a single-element array" is the fastest possible run, but best case is defined for inputs of arbitrary size n.

All Data Structures & Algorithms questions · placement mock tests