4.3 Algorithms

Question 1

2017 A-Level paper 1

State the time complexity for the bubble sort algorithm in terms of n, where n is the number of items in the list to be sorted. [1]

Answer 1

O(n^2)

A. other ways of indicating n^2

Question 2

2017 A-Level paper 1

Explain why the bubble sort algorithm has the time complexity O(n^2) [2]

Answer 2

In each pass through the list n items will be examined;
There will be (at most) n passes through the list;