Measures and methods to determine efficiency, Big O notation

Measures and methods to determine the efficiency of different algorithms, Big O notation (constant, linear, polynomial, exponential and logarithmic complexity).

2.3.1 Algorithms

Algorithms — Note 3 of 6

Candidates need to understand how the efficiency of an algorithm is measured using Big O notation, including constant, linear, polynomial, exponential and logarithmic complexity. Candidates need to be able to recognise and draw each complexity on a graph and read and write the notation.

What you need to know

Big O notation describes how the time (or space) an algorithm needs grows as the input size grows, ignoring constant factors. It lets algorithms be compared independently of the hardware they run on.

What to know

Constant, O(1): time does not change with input size, e.g. accessing an array element by index.
Logarithmic, O(log n): time grows very slowly as n increases because the problem is halved each step, e.g. binary search.
Linear, O(n): time grows in direct proportion to n, e.g. linear search.
Polynomial, O(n²) (or O(n^k)): time grows with the square (or other power) of n, often from nested loops, e.g. bubble sort.
Exponential, O(2^n): time doubles with each extra item; quickly becomes impractical, e.g. checking every subset of a set.
O(n log n) lies between linear and polynomial, e.g. merge sort.
Rules: keep only the dominant (fastest-growing) term and remove constants, e.g. 3n² + 5n + 2 is O(n²).
Rule of thumb: a single loop over the data is O(n); a loop nested inside another loop over the same data is O(n²); halving the data each step is O(log n).

Key terms

Big O notation: A way of expressing the upper bound of an algorithm's time or space complexity as a function of the input size n.

Exam technique

Tip:You should be able to recognise and sketch the graph shape of each complexity and read and write the notation.

Code examples

Order of growth from fastest to slowest

text

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)

n = 1,000:
  O(log n)   ~ 10 steps
  O(n)       1,000 steps
  O(n log n) ~ 10,000 steps
  O(n^2)     1,000,000 steps
  O(2^n)     more steps than atoms in the universe