Loading…
Free A-Level Computer Science guide
Count the work, state the input size and explain the growth. This OCR A-Level H446 guide connects loops, searches and recursive algorithms with time and space complexity using original examples.
Content owner: Michael Print · Written for A-Level learners · Checked against official specifications
Time complexity describes how the amount of work grows as input size n grows. Space complexity describes how memory use grows. Big O notation gives an asymptotic upper bound on that growth, ignoring constant factors and lower-order terms.
In examination comparisons, give the tightest usual growth class you can justify and state the case: for example, linear search has O(n) worst-case time. Saying only “it is fast” does not explain its behaviour on larger inputs.
You should be able to trace loops and distinguish a list index from its value. Revisit selection and loops. The existing searching and sorting guide provides the search algorithms used in our comparisons.
Scope: OCR H446 §2.3.1(b–d). We assume constant-time indexed access and fixed-cost arithmetic/comparisons unless stated otherwise. Space figures below mean auxiliary space: working memory beyond the supplied input.
Define n
Say what input size measures, such as the number of array items.
Choose the operation
Count a relevant action, such as a comparison or the pair counter’s increment.
Count repetitions
Read the actual loop bounds: separate loops add their work; nested loops may multiply it.
Simplify the growth
Identify the dominant term and remove constant factors and lower-order terms.
State the resource and case
Give time or auxiliary space, and identify best, average or worst case where relevant.
| Class | Name | Typical reason or example |
|---|---|---|
| O(1) | Constant | Read one item by array index |
| O(log n) | Logarithmic | Repeatedly halve a candidate range |
| O(n) | Linear | Visit each of n items once |
| O(n log n) | Linearithmic | Linear work at each of log n merge-sort levels |
| O(n²) | Quadratic (polynomial) | Compare all pairs of n items |
| O(2^n) | Exponential | Explore include/exclude choices for all n items |
Quadratic is one polynomial example; powers such as n³ are polynomial too. n log n combines two factors and differs from log n.
The logarithm's base changes a constant factor, so Big O omits it. Our numerical examples use base 2.
| n | 1 | log₂ n | n | n log₂ n | n² | 2^n |
|---|---|---|---|---|---|---|
| 8 | 1 | 3 | 8 | 24 | 64 | 256 |
| 16 | 1 | 4 | 16 | 64 | 256 | 65536 |
| 32 | 1 | 5 | 32 | 160 | 1024 | 4294967296 |
Use the table to check how each model changes:
log₂ n.2^n, increasing n by 1 doubles the value; doubling n squares the previous value.These relationships describe model functions, rather than a particular computer's measured timings.
Worked example
Suppose the chosen operation occurs 3n² + 8n + 12 times. As n becomes large, the quadratic term dominates the linear and constant terms. Drop the constant multiplier 3 and the smaller terms: the tight growth class is O(n²).
n + n = 2n visits, giving O(n).n × n = n² visits, giving O(n²).Check the actual bounds: nested loops need not both run n times.
This algorithm considers each distinct pair of positions once. The inner loop depends on first, so it does not run n times on every outer iteration.
def count_pairs(n):
# Precondition: n is a non-negative integer.
count = 0
for first in range(n):
for second in range(first + 1, n):
count = count + 1
return count
for size in [4, 8, 16]:
print(size, count_pairs(size))
# 4 6
# 8 28
# 16 120| first | second values | Increments this iteration | Cumulative count |
|---|---|---|---|
| 0 | 1, 2, 3 | 3 | 3 |
| 1 | 2, 3 | 2 | 5 |
| 2 | 3 | 1 | 6 |
| 3 | None | 0 | 6 |
For n items, count (n − 1) + (n − 2) + … + 1 + 0 = n(n − 1)/2. Expanding gives (n² − n)/2, so the time class is O(n²).
A fixed number of loop variables and one counter give O(1) auxiliary space under our model. Empty and one-item inputs both produce 0.
def halving_steps(n):
# Precondition: n is a positive integer.
steps = 0
while n > 1:
n = n // 2
steps = steps + 1
return steps
for size in [1, 16, 32]:
print(size, halving_steps(size))
# 1 0
# 16 4
# 32 5| Iteration | n before | n after integer division | steps after |
|---|---|---|---|
| 1 | 16 | 8 | 1 |
| 2 | 8 | 4 | 2 |
| 3 | 4 | 2 | 3 |
| 4 | 2 | 1 | 4 |
After k exact halvings, a power-of-two input has size n / 2^k. Reaching 1 means 2^k = n, so k = log₂ n. Non-power-of-two inputs use integer division; the same O(log n) class applies.
This function counts halvings, not a binary search's item inspections. A search may also inspect the final one-item range. Binary search on an already sorted, directly indexed array has O(log n) worst-case time, but sorting an unsorted collection first has its own cost.
For each of n items, there are two choices: include it or exclude it. Exploring every possibility produces 2^n complete choices. This deliberately inefficient counting function recomputes both smaller branches.
def count_choices(n):
# Precondition: n is a non-negative integer.
if n == 0:
return 1
include = count_choices(n - 1)
exclude = count_choices(n - 1)
return include + exclude
print(count_choices(0)) # 1
print(count_choices(4)) # 16Space uses the stated fixed-size integer model. Returning a count does not retain every generated subset.
Returning a count does not store every subset. A different algorithm that retains every generated subset has a different space cost. Time is the total work over the run; space is the memory needed at its peak.
Choose from the whole task, including preparation and updates:
Separate the cases. Linear search can match the first item in O(1) time but may inspect all n items in O(n). An average-case claim needs assumptions about inputs, such as where a successful target is equally likely to occur.
A copied n-item list adds O(n) auxiliary space, even if a later loop uses one counter. A recursive chain can add stack space without an explicit list.
Lower growth does not guarantee shorter measured time on small inputs. Constant factors, implementation and hardware still affect runtime.
These four original questions total 17 marks. Use the model stated on this page and the tightest standard growth class. The guidance is indicative and independently written.
An algorithm performs 5n² + 2n + 7 counted operations. Give its tight growth class in Big O and explain the simplification.
Indicative answer:
For count_pairs(5), state how often count = count + 1 executes. Give the general count for n, its time class and its auxiliary space class, explaining the space answer.
Indicative answer:
4 + 3 + 2 + 1 + 0 = 10 increments (1).n(n − 1)/2 increments (1).How many iterations does halving_steps perform for inputs 64 and 128? Give its time class and explain how the change in the count supports your answer.
Indicative answer:
A program makes many lookups in an already sorted array of n items, with constant-time indexed access. Recommend linear or binary search and justify it.
Before searching, it makes one complete copy of the array. Explain that copy's auxiliary space cost and why this differs from the search's time cost.
Indicative answer:
The complete copy-and-search operation takes O(n) time because copying dominates. If one copy is reused, its cost can be spread over many lookups.
Checked against OCR H446 specification version 3.0 (2026), printed page 12: §2.3.1(b), execution time and space; (c), efficiency and Big O; and (d), complexity comparisons. Examples also cover common n log n analysis.
Code checked with Python 3.12.14. Content reviewed 10 October 2026; editorial draft awaiting tutor approval.
These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.
Found an error? Email a correction.
Use the free examples first, then explore one-to-one tuition if guided practice would help.