Two algorithms that do the same job can be compared by the time they take and the memory they use. Big O notation describes how each of these grows as the amount of data grows, so you can choose the right algorithm before writing a line of code.
Algorithms that perform the same task are compared by the time taken (the number of basic steps, such as comparisons) and the memory used, as the number of data items n grows. Big O notation gives the order of growth in the worst case: keep only the dominant term and drop constants, so 3n2 + 5n + 2 steps is O(n2). Time complexity ranks O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n). Space complexity uses the same notation for extra memory: an in-place sort is O(1), a copy of the data is O(n).
Fig. 1: the common orders of growth. For small n they are close; as n grows, O(n2) and O(2n) quickly become unusable.
Section 01
Fair comparisons.
Timing two programs with a stopwatch is not a fair test: the result depends on the processor, the language, the compiler and whatever else is running. Instead, count the basic operations the algorithm performs as a function of n, the number of data items.
Time taken: count the key operation, such as comparisons in a search or sort, or how often the innermost loop body runs.
Memory used: count the extra storage the algorithm needs on top of the input data: variables, copies of arrays, stack frames for recursive calls.
Best, average and worst case: the same algorithm can do very different amounts of work on different data. A linear search finds the first element in 1 comparison but needs n if the item is missing. Big O normally quotes the worst case, the guarantee.
Growth matters most: an algorithm that is slightly slower on 10 items may be far faster on a million. The question is how the work grows as n grows.
Count ← 0
FOR i ← 1 TO n
FOR j ← 1 TO n
Count ← Count + 1
NEXT j
NEXT i
Worked example Count the steps
How many times is Count ← Count + 1 executed by the code above when n = 10? What if the inner loop is changed to FOR j ← i TO n?
Original: the inner loop runs n times for each of the n values of i, so n × n = 10 × 10 = 100.
Changed: when i = 1 the inner loop runs 10 times, when i = 2 it runs 9 times, ..., when i = 10 it runs once.
Answer:100 and 55. Both grow with n2, so both are O(n2): halving the work does not change the order of growth
Your turn
A loop runs FOR i ← 1 TO n and its body contains three assignments and no other loop. How many assignments are executed for n = 50, and what is its time complexity?
3 × 50 = 150. The work is 3n, which grows in proportion to n: O(n).
Examiner trap
"Algorithm A is faster because it took 0.3 seconds" earns nothing. Compare the number of operations as n increases, or the Big O order.
Section 02
Big O notation.
In the lab, compare the two searches, then the two sorts, as the list grows. Switch the sorts to data that is already sorted and watch both curves flatten from n2 to n: the best case and the worst case have different orders.
Order
Name
Example
If n doubles, the time...
O(1)
constant
push or pop on a stack; access List[i]
stays the same
O(log n)
logarithmic
binary search; search a balanced binary tree
grows by one step
O(n)
linear
linear search; find an item in a linked list
doubles
O(n log n)
linearithmic
efficient sorts such as merge sort
slightly more than doubles
O(n2)
polynomial (quadratic)
bubble sort, insertion sort; nested loops over the data
is multiplied by 4
O(2n)
exponential
naive recursive Fibonacci; trying every subset
doubles each time n rises by just 1
Dominant term: for large n the highest power swamps everything else. With n = 1000, 3n2 + 5n + 2 = 3 005 002, and the 5n + 2 part is under 0.2% of it.
Drop constants: 3n2 and 0.5n2 are both O(n2). Constants depend on the machine; the growth does not.
Loops: one loop over the data is usually O(n); a loop nested inside another, both over the data, is usually O(n2); a loop that halves the data each time is O(log n).
Worked example Predict the run time
An O(n2) sort takes 2 seconds for 1000 items. Estimate its time for 3000 items. How would an O(n) algorithm that also takes 2 seconds for 1000 items compare?
3000 is 3 times 1000.
O(n2): time is multiplied by 32 = 9, so 2 × 9 = 18 seconds.
O(n): time is multiplied by 3, so 2 × 3 = 6 seconds.
Answer: About 18 s for the O(n2) sort against about 6 s for the O(n) algorithm
Your turn
Give the Big O time complexity of an algorithm that makes 4n + 7 log2 n + 20 comparisons, and of one that makes 0.01n3 + 500n comparisons.
The dominant terms are 4n and 0.01n3, so O(n) and O(n3).
Examiner trap
O(log n) does not mean "fewer than n" for every n, and O(n2) does not give an exact count. Big O describes how the work grows; for very small n a "worse" algorithm can still be quicker.
Stage 1 · Learn
Check what the sim just showed you
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
In the lab, how does the binary search curve change as the list gets longer?
Quick check+10 XP
What is the time complexity of an algorithm that makes 5n2 + 100n + 3 comparisons?
Quick check+10 XP
Why is the number of operations a better measure than the time in seconds?
Quick check+10 XP
An insertion sort of n items uses only Key, i and j as extra variables. What is its space complexity?
Section 03
Space complexity.
Memory is the second criterion. Big O is used in the same way: how does the extra memory an algorithm needs grow as n grows? Often you can trade one resource for the other.
Algorithm
Time (worst case)
Extra space
Linear search
O(n)
O(1)
Binary search (iterative)
O(log n)
O(1)
Bubble sort, insertion sort
O(n2)
O(1): in place
Find in a binary search tree
O(log n) if balanced, O(n) if not
O(1) iterative
Push, pop, enqueue, dequeue
O(1)
O(1)
Recursive factorial of n
O(n)
O(n): n stack frames
O(1) space: a fixed number of extra variables (Temp, Key, Low, High, Mid) whatever the size of the data.
O(n) space: the extra memory grows with the data, for example copying the array, building a second sorted list, or recursion that goes n calls deep.
Time against memory: a hash table spends extra memory on empty slots to get near O(1) look-ups; keeping data sorted costs time on every insert but makes O(log n) searches possible.
Worked example Choose an algorithm
A device with very little RAM must sort 200 sensor readings once an hour. Algorithm P is O(n log n) time but needs a second array of n items. Algorithm Q is an insertion sort. Which should be chosen?
Time: for n = 200, n2 = 40 000 against n log2 n of about 1529. Q does more work, but 40 000 steps once an hour is trivial for a processor.
Space: P needs O(n) extra memory for the second array; Q sorts in place in O(1) extra memory.
The binding constraint here is memory, not time.
Answer: Choose Q, the insertion sort: its O(1) space suits the small RAM, and its O(n2) time is acceptable for 200 items once an hour
Your turn
Why is a binary search tree built from data that arrives in sorted order a poor choice for searching?
Every new value is larger than the last, so each becomes a right child and the tree is a single branch. Finding an item can need n comparisons: the search is O(n) instead of O(log n).
Examiner trap
Do not confuse the two criteria. "It uses less memory" is a space argument; "it makes fewer comparisons" is a time argument. Say which one you mean and link it to n.
Stage 2 · Exam
Exam-style questions
Unlocks once the four checks above are done. Worth more XP, written to A Level Paper 3 and Paper 4 standard.
Finish the four checks above to unlock the exam questions
Exam style+20 XP
An O(n2) algorithm takes 5 seconds for 2000 items. About how long will it take for 4000 items?
Exam style+20 XP
Which list is in order from slowest-growing to fastest-growing?
Exam style+20 XP
What is the worst-case time complexity of finding an item in a linked list of n nodes?
Exam style+20 XP
Which algorithm has exponential time complexity?
Skill unlocked
Big O notation, mastered.
This skill is now recorded on your profile. Keep the chain going.