Time complexity of the sorting algorithms

Overview

Worst-case time complexity of a bubble sort, why a bubble sort is O(n²) in the worst case and worst-case time complexity of an insertion sort.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   State the worst-case time complexity of a bubble sort.

   Model answer

   A bubble sort has a worst case of O(n²).

2. 2

   Explain why a bubble sort is O(n²) in the worst case.

   Model answer

   A bubble sort makes up to n passes over the list. Each pass makes up to n comparisons, so the total is proportional to n².

3. 3

   State the best-case complexity of a bubble sort that stops when a pass makes no swaps.

   Model answer

   The best case is O(n). A single pass over an already sorted list makes no swaps and the algorithm stops.

4. 4

   State the worst-case time complexity of an insertion sort.

   Model answer

   An insertion sort has a worst case of O(n²).

5. 5

   When does an insertion sort hit its worst case?

   Model answer

   An insertion sort hits its worst case when the list is in reverse order. Every new item must be moved past all of those already placed.

6. 6

   State the best-case complexity of an insertion sort.

   Model answer

   The best case is O(n), reached when the list is already in order. Each item is compared once with its predecessor and stays put.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.