A-level Computer Science revision · Data structures and algorithms

Big O complexity

The idea

Big O notation describes how an algorithm's time or space grows with input size n, keeping the dominant term. Constant O(1), logarithmic O(log n), linear O(n), polynomial O(n²), exponential O(2ⁿ). Better complexity matters most for large inputs.

  1. Count how the work grows with n.
  2. Keep only the fastest-growing term; drop constants.
  3. Compare: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).

Watch out An O(n²) algorithm can be faster than O(n) for very small n; Big O describes growth.

See it worked

Worked example

What is the time complexity of a loop nested inside another, each running n times?

  1. Inner loop: n steps per outer iteration.
  2. Outer: n iterations.
  3. n × n = O(n²).

Answer O(n²)

Your turn

Question 11 mark

What is the time complexity of binary search?

Choose one
Question 22 marks

An algorithm's time is proportional to n². It takes 4 seconds for n = 1000. Roughly how long would it take for n = 2000, in seconds?

Question 31 mark

Which complexity grows fastest as n increases?

Choose one

A-level Computer Science Pro, OCR H446

A-level Computer Science Pro

£119 once

Price rises to £199 on 1 January. Save £80 by joining before then.

At least 12 months of access

By paying you agree to our Terms and get access straight away, which ends your 14-day cancellation right.

No VAT is charged.

Independent practice for OCR A-level Computer Science (H446), not endorsed by OCR.

Privacy · Terms