EnglandComputer ScienceSyllabus dot point

How do we measure and compare the efficiency of algorithms using Big-O notation?

Big-O notation for time and space complexity: the constant, logarithmic, linear, linearithmic, polynomial and exponential complexity classes, how to determine the Big-O of an algorithm, and using it to compare and judge the suitability of algorithms.

An OCR H446 answer on Big-O notation: the constant, logarithmic, linear, linearithmic, polynomial and exponential complexity classes for time and space, how to determine an algorithm's Big-O, and using it to compare algorithms and judge their suitability.

Generated by Claude Opus 4.814 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Quick answer

Big-O notation describes how an algorithm's running time or memory use grows as the input size $n$ grows, giving the worst-case order of growth so algorithms can be compared independently of hardware. Constants and lower-order terms are dropped because the fastest-growing term dominates for large $n$ , so $3n^2 + 5n$ is $O(n^2)$ . The common classes, from most to least efficient, are: constant $O(1)$ (independent of $n$ , like array access by index), logarithmic $O(\log n)$ (binary search), linear $O(n)$ (linear search), linearithmic $O(n \log n)$ (merge and quick sort), polynomial $O(n^2)$ and higher (bubble sort, nested loops), and exponential $O(2^n)$ (naive brute force), which becomes infeasible quickly. To find an algorithm's Big-O, count the dominant repeated work: a single loop is $O(n)$ , a loop nested in a loop is $O(n^2)$ , halving each step gives $O(\log n)$ . Big-O lets you choose the algorithm that scales best for the expected data size.

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

OCR wants the meaning of Big-O for time and space, the standard complexity classes in order, how to determine an algorithm's Big-O (from loops and recursion), and how to use Big-O to compare algorithms and judge suitability. This is analysis: expect to order classes, give examples, and determine the complexity of a code fragment.

The answer

What Big-O measures

Why constants and lower-order terms are dropped

The complexity classes and determining Big-O

Key fact

From most to least efficient for large $n$ : constant $O(1)$ (cost independent of $n$ , such as accessing array[i]); logarithmic $O(\log n)$ (the input is repeatedly halved, such as binary search); linear $O(n)$ (work proportional to $n$ , such as linear search); linearithmic $O(n \log n)$ (such as merge sort and average quick sort); polynomial $O(n^2)$ , $O(n^3)$ and higher (nested loops, bubble and insertion sort); and exponential $O(2^n)$ (doubling with each extra element, such as naive brute-force search of all subsets), which becomes infeasible very quickly. To determine an algorithm's Big-O, identify the dominant repeated work: a single loop over $n$ items is $O(n)$ ; a loop nested inside another, each $n$ times, is $O(n^2)$ ; repeatedly halving the data is $O(\log n)$ ; combining a halving with linear work per level gives $O(n \log n)$ .

Determine and compare complexities

An algorithm A uses two nested loops each running $n$ times. Algorithm B halves a sorted list each step. Determine each one's Big-O and decide which scales better.

step 1: Analyse algorithm A

The outer loop runs $n$ times; for each, the inner loop runs $n$ times, so the body executes about $n \times n = n^2$ times. Time complexity: $O(n^2)$ (polynomial).

step 2: Analyse algorithm B

Halving the data each step means the number of steps to reduce $n$ items to one is $\log_2 n$ . Time complexity: $O(\log n)$ (logarithmic).

step 3: Compare growth for large n

At $n = 1\,000\,000$ : A does about $10^{12}$ operations, while B does about $20$ ( $\log_2 1\,000\,000 \approx 20$ ). The gap is astronomical and grows with $n$ .

step 4: Conclude

Algorithm B ( $O(\log n)$ ) scales far better than A ( $O(n^2)$ ). For large inputs, the lower complexity class dominates any constant-factor differences, so B is the suitable choice when the data can be kept sorted.

Examples in context

Choosing binary search ( $O(\log n)$ ) over linear search ( $O(n)$ ) is the difference between 20 and a million comparisons on a million items. Quadratic sorts become unusable on large datasets, so libraries use $O(n \log n)$ sorts. Exponential algorithms (naive travelling salesman) are why heuristics exist. Database query planners reason about complexity to pick efficient strategies. OCR ties Big-O to the searching, sorting and graph algorithms (each labelled with its complexity) and to the computational methods that tame intractable problems.

Try this

Q1. State what Big-O notation describes. [1 mark]

Cue. How an algorithm's running time (or space) grows as the input size $n$ grows (its worst-case order of growth).

Q2. Give the time complexity of an algorithm with a single loop running $n$ times, and one with two such loops nested. [2 marks]

Cue. Single loop $O(n)$ ; nested loops $O(n^2)$ .

Q3. Order $O(n)$ , $O(1)$ , $O(n^2)$ and $O(\log n)$ from most to least efficient. [1 mark]

Cue. $O(1)$ , $O(\log n)$ , $O(n)$ , $O(n^2)$ .

Exam-style practice questions

Practice questions written in the style of OCR exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

OCR 20206 marksOrder the complexity classes

O(1)

O(n^2)

O(\log n)

O(n)

and

O(2^n)

from most to least efficient for large

n

, and give an example algorithm for three of them.

Show worked answer →

Ordering (up to 3), most efficient first: $O(1)$ , $O(\log n)$ , $O(n)$ , $O(n^2)$ , $O(2^n)$ . (Constant beats logarithmic beats linear beats quadratic beats exponential.)

Examples (up to 3), any three: $O(1)$ accessing an array element by index; $O(\log n)$ binary search; $O(n)$ linear search; $O(n^2)$ bubble or insertion sort; $O(2^n)$ a naive recursive solution to the subset/travelling-salesman-style problem. Markers reward the correct efficiency order and valid example algorithms. A common error is ranking $O(n^2)$ as better than $O(2^n)$ incorrectly, or vice versa; exponential is the worst.

OCR 20226 marksExplain what Big-O notation describes, why constants and lower-order terms are dropped, and determine the time complexity of an algorithm that contains a single loop nested inside another loop, each running

n

times.

Show worked answer →

What Big-O describes (up to 2): Big-O describes how an algorithm's running time (or space) grows as the size of the input $n$ grows, giving the worst-case order of growth so algorithms can be compared independently of hardware.

Dropping constants and lower-order terms (up to 2): for large $n$ the fastest-growing term dominates, so constant factors and lower-order terms become insignificant; $3n^2 + 5n + 2$ is written $O(n^2)$ because the $n^2$ term dominates. This captures scalability, not exact timings.

Nested loops (up to 2): a loop running $n$ times with another loop running $n$ times inside it performs about $n \times n = n^2$ operations, so the time complexity is $O(n^2)$ . Markers reward growth-with-input-size, dominance of the highest-order term, and $O(n^2)$ for the nested loops.

Related dot points

Sources & how we know this

OCR AS and A Level Computer Science (H046, H446) specification — OCR (2015)