Algorithms and Big O Complexity
Searching, sorting, traversals, Dijkstra and A star, and Big O analysis with the reasoning behind each complexity class.
Big O and searching
Big O notation
Big O describes how the resources an algorithm requires grow as the input size n grows. It describes the worst case unless stated otherwise, and it discards constants and lower order terms because only the dominant behaviour matters at scale.
| Complexity | Name | Example | n = 1,000,000 |
|---|---|---|---|
| O(1) | Constant | Array access by index, hash table lookup | 1 operation |
| O(log n) | Logarithmic | Binary search, balanced BST | about 20 |
| O(n) | Linear | Linear search, one pass over a list | 1,000,000 |
| O(n log n) | Linearithmic | Merge sort, quicksort average case | about 20,000,000 |
| O(n2) | Polynomial | Bubble sort, insertion sort, nested loops | 1,000,000,000,000 |
| O(2n) | Exponential | Brute force subset problems | Infeasible |
| O(n!) | Factorial | Brute force travelling salesman | Utterly infeasible |
Space complexity describes memory growth in the same way. Merge sort is O(n log n) in time but O(n) in space, which is exactly the trade off against bubble sort's O(1) space.
Linear search
Check each element in turn. O(n) worst case. Works on unsorted data, requires no preparation.
Binary search
Requires sorted data. Compare with the middle element and discard half the remaining range each time.
function binarySearch(list, target)
low = 0
high = list.length - 1
while low <= high
mid = (low + high) DIV 2
if list[mid] == target then
return mid
elseif list[mid] < target then
low = mid + 1
else
high = mid - 1
endif
endwhile
return -1
endfunctionO(log n), because each comparison halves the search space. On a million items that is about twenty comparisons rather than a million.
Sorting costs O(n log n), which is more than a single linear search. But if the data will be searched many times, that cost is paid once and every subsequent search drops from O(n) to O(log n).
- Each curve shows how the work grows as the input gets bigger.
- From flat, to slow, to straight, to steep, to explosive: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
- Linear search looks at every item in turn from the start, so it can be slow.
- Binary search checks the middle and throws half the list away each time.
- 3 looks against 10. The longer the list, the bigger the gap, but binary search needs the list sorted.
Sorting algorithms
Bubble sort, O(n2)
Repeatedly compare adjacent pairs and swap if out of order. After each pass the largest remaining value is in place. With a swap flag it terminates early on sorted data, giving O(n) best case.
Space O(1). Simple, and unusable at scale.
Insertion sort, O(n2)
Build a sorted section at the front, inserting each next item into its correct place. Space O(1). Best case O(n) on nearly sorted data, and it can sort a stream as items arrive.
Merge sort, O(n log n)
Divide and conquer. Split the list until each part holds one item, then repeatedly merge sorted sub lists.
function mergeSort(list)
if list.length <= 1 then
return list
endif
mid = list.length DIV 2
left = mergeSort(list[0 to mid-1])
right = mergeSort(list[mid to end])
return merge(left, right)
endfunctionConsistently O(n log n) in every case, which is its great strength. Space O(n), because the sub lists must be stored, and that is its cost.
Quicksort, O(n log n) average
Choose a pivot, partition so smaller values are on the left and larger on the right, then recursively sort each partition. Average O(n log n) with better constants than merge sort, so it is usually faster in practice, and space O(log n) for the recursion stack. Worst case O(n2) when the pivot is consistently the smallest or largest element, which is why practical implementations choose the pivot carefully.
Choosing
| Situation | Algorithm |
|---|---|
| Small or nearly sorted list | Insertion sort |
| Guaranteed performance required | Merge sort |
| Best average speed, memory limited | Quicksort |
| Very limited memory | Insertion or bubble sort |
| Teaching the concept | Bubble sort |
Sorting algorithm visualiser
Run bubble, insertion, merge and quick sort side by side and count the comparisons. This tool needs JavaScript, so turn it on to use it. Everything you need to answer the exam question is explained in the text above.
- Divide the list in half, again and again.
- Stop when every group is a single item. One item is already sorted.
- Merge groups back together, taking the smaller front item each time, until one sorted list is left.
- Choose a pivot. Here it is the first item.
- Partition: smaller items to its left, larger to its right. The pivot is now in its final position.
- Sort each part the same way, recursively. A part of one item is already sorted.
- Join the parts in order. There is no merge step.
- The starting order. Ana and Cat have the same score.
- A stable sort keeps Ana before Cat, as they were.
- An unstable sort may swap them.
- Compare the sorts on best, average and worst case time, on extra memory, and on whether they are stable.
- Choose by the situation: nearly sorted, guaranteed speed, or fastest on average.
Graph and tree algorithms
Traversals
Depth first search goes as deep as possible before backtracking, using a stack or recursion. Suits maze solving, topological sorting and finding any path.
Breadth first search explores all neighbours at the current depth before going deeper, using a queue. Finds the shortest path in an unweighted graph, and suits finding the nearest node.
Tree traversals: pre order visits node, left, right and is used for copying a tree. In order visits left, node, right and outputs a binary search tree in ascending order. Post order visits left, right, node and is used for deletion and postfix expressions.
Dijkstra's shortest path
Finds the shortest path from one source to all other nodes in a weighted graph with non negative weights.
- Set the source distance to 0 and every other to infinity, and mark all nodes unvisited.
- From the unvisited nodes, select the one with the smallest known distance, the current node.
- For each unvisited neighbour, calculate the distance through the current node. If it is smaller than the recorded distance, replace it and record the current node as its predecessor.
- Mark the current node visited.
- Repeat from step 2 until the destination is visited or no reachable unvisited node remains.
The predecessor records allow the actual path to be reconstructed by working backwards from the destination.
Complexity O(n2) with a simple implementation, improving to O(E + V log V) with a priority queue.
Once a node is marked visited its distance is assumed final, and a negative edge could later produce a shorter route, invalidating that assumption.
A star
An extension of Dijkstra using a heuristic to guide the search towards the goal.
At each step it selects the node with the lowest value of:
f(n) = g(n) + h(n)
where g(n) is the actual cost from the start to n, and h(n) is a heuristic estimate of the cost from n to the goal, commonly the straight line distance.
Because it prefers nodes that appear to lead towards the goal, A star explores far fewer nodes than Dijkstra and reaches the answer much faster. It is guaranteed to find the optimal path provided the heuristic is admissible, meaning it never overestimates the true remaining cost.
Dijkstra is A star with h(n) set to zero for every node.
- A weighted graph: each edge has a cost, such as a distance or a time.
- The shortest route is not always the one with the fewest edges: here it takes five edges to save two units.
- The working table holds each node's best distance so far and the node it came via.
- Always visit the unvisited node nearest the start, then update its neighbours. Read the route back through the via column.
- Breadth first: visit everything one step away, then everything two steps away, and so on. It uses a queue.
- Depth first: follow one branch as far as it goes, then back up and try the next. It uses a stack, or recursion.
- Dijkstra explores in every direction, cell by cell in order of distance from the start.
- A* adds a heuristic, a guess of the distance still to go, so it heads for the goal.
- The difference is one guess: g for Dijkstra, g plus h for A*. The heuristic must never overestimate.
Key terms you must be able to define
- Big O notation
- A description of how an algorithm's resource use grows with input size, in the worst case.
- Time complexity
- How the number of operations grows as the input size increases.
- Space complexity
- How the memory required grows as the input size increases.
- Linear search
- Checking each element in turn, O(n), requiring no ordering.
- Binary search
- Halving a sorted range at each comparison, O(log n).
- Merge sort
- A divide and conquer sort with consistent O(n log n) time and O(n) space.
- Quicksort
- A partitioning sort averaging O(n log n) with O(n squared) worst case.
- Pivot
- The element around which quicksort partitions the data.
- Depth first search
- A traversal exploring as deep as possible before backtracking, using a stack.
- Breadth first search
- A traversal exploring all nodes at one depth before going deeper, using a queue.
- Dijkstra's algorithm
- An algorithm finding the shortest path in a weighted graph with non negative weights.
- A star
- A pathfinding algorithm using a heuristic estimate to guide the search towards the goal.
- Admissible heuristic
- A heuristic that never overestimates the remaining cost, guaranteeing an optimal result.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
- State a complexity and justify it, for example that binary search is O(log n) because each comparison halves the range
- Give the space complexity as well as the time complexity when comparing sorts
- Know that DFS uses a stack and BFS uses a queue, and what each is therefore good at
- Trace Dijkstra with a full table of distances, predecessors and visited nodes
- Explain A star's f = g + h and why an admissible heuristic guarantees optimality
- Justify a choice of algorithm against the properties of the data in the question
Mistakes that cost marks here
- Quoting a complexity with no justification for why it is that class.
- Comparing sorts on time only, ignoring merge sort's O(n) space cost.
- Applying binary search to unsorted data.
- Using Dijkstra on a graph with negative weights.
- Saying A star is always faster with no mention of the heuristic having to be admissible.
- Confusing depth first and breadth first, and which structure each uses.
Dijkstra devised his shortest path algorithm in about twenty minutes in 1956 while sitting in a cafe with his fiancee, without pencil or paper. He said the absence of paper forced him to avoid all avoidable complexity.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LIt describes how resource use grows as the input size increases
- LIt describes the worst case unless otherwise stated
- LConstants and lower order terms are ignored because only dominant growth matters at scale
Big O notation describes how the resources an algorithm requires, usually time but also memory, grow as the size of the input increases, and unless stated otherwise it describes the worst case, giving an upper bound on the behaviour. Constants and lower order terms are discarded because they become insignificant as the input grows. An algorithm taking 3n squared plus 100n plus 5000 operations is written as O(n squared), because once n is large the squared term dominates completely and the difference between 3n squared and n squared is a fixed multiple that does not change the fundamental scaling behaviour. This matters because the purpose of Big O is to compare how algorithms behave as data grows, not to predict exact runtimes on a particular machine.
- LMerge sort is O(n log n) in all cases including the worst
- LQuicksort averages O(n log n) but degrades to O(n squared) in the worst case
- LThe quicksort worst case occurs when the pivot is consistently the smallest or largest element
- LMerge sort requires O(n) additional space for the sub lists
- LQuicksort sorts largely in place using only O(log n) stack space
Merge sort has time complexity O(n log n) in the best, average and worst cases alike, because it always divides the list exactly in half regardless of the data and always performs the same merging work. Quicksort has average time complexity O(n log n) and in practice usually outperforms merge sort because its constant factors are smaller, but its worst case is O(n squared). That worst case occurs when the chosen pivot is consistently the smallest or largest remaining element, so each partition removes only one item rather than roughly half, and it arises naturally if the first element is chosen as the pivot on data that is already sorted. Practical implementations avoid it by choosing the pivot as the median of three candidates or at random. Space is where the comparison reverses. Merge sort requires O(n) additional memory because the sub lists produced by the divide phase must be stored while merging, whereas quicksort partitions the array in place and needs only O(log n) stack space for its recursive calls. The choice therefore depends on priorities: merge sort when guaranteed performance is essential or when sorting data that does not fit in memory, quicksort when average speed matters most and memory is constrained.
- LThe source node distance is set to zero and all others to infinity
- LThe unvisited node with the smallest known distance is selected as the current node
- LFor each unvisited neighbour the distance through the current node is calculated
- LIf that distance is smaller than the recorded distance it replaces it
- LThe predecessor is recorded so the path can be reconstructed
- LThe current node is marked visited and the process repeats until the destination is reached
Dijkstra's algorithm begins by setting the distance to the source node as zero and the distance to every other node as infinity, with all nodes marked unvisited. It then repeatedly selects, from among the unvisited nodes, the one with the smallest recorded distance, and treats this as the current node. For each unvisited neighbour of the current node, it calculates the distance to that neighbour by travelling through the current node, which is the current node's distance plus the weight of the connecting edge. If this calculated distance is less than the distance already recorded for that neighbour, the recorded distance is replaced with the new smaller value and the current node is stored as that neighbour's predecessor. Once all neighbours have been considered, the current node is marked as visited and will not be examined again, because its distance is now known to be final. The process repeats, always choosing the unvisited node with the smallest distance, until the destination has been visited or no reachable unvisited node remains. The shortest path itself is then recovered by starting at the destination and following the chain of recorded predecessors back to the source, which yields the route in reverse.
- LA star adds a heuristic estimate of the remaining cost to the goal
- LNodes are selected by the lowest value of f equals g plus h
- LDijkstra explores outwards in all directions equally
- LA star prioritises nodes appearing to lead towards the goal, so it examines fewer nodes
- LIt still finds the optimal path provided the heuristic never overestimates
Dijkstra's algorithm always expands the unvisited node with the smallest distance from the source, which means it explores outwards from the start in every direction equally, discovering shortest paths to nodes that lie entirely away from the destination before it happens to reach the destination itself. A star modifies the selection rule by adding a heuristic estimate of the remaining cost from each node to the goal, so it chooses the node with the lowest value of f, where f equals g plus h, g being the actual cost accumulated from the start and h being the estimated cost still to travel. Because a node lying in the direction of the goal receives a low h value, it is selected in preference to a node that is equally close to the start but heading away, so the search is directed rather than uniform and typically examines a small fraction of the nodes that Dijkstra would. Crucially, A star still guarantees the optimal path provided the heuristic is admissible, meaning it never overestimates the true remaining cost, since underestimating simply means the algorithm may explore a few extra nodes rather than committing to a suboptimal route. Straight line distance is the standard admissible heuristic for geographic pathfinding, since no actual route can be shorter than a straight line. Dijkstra can be seen as the special case of A star where h is zero everywhere.
- LLinear search is O(n) and would examine up to 10 million records per search
- LLinear search requires no ordering but is far too slow at this scale
- LBinary search is O(log n), needing about 24 comparisons
- LBinary search requires the data to be kept sorted, which costs time on insertion
- LA hash table gives average O(1) lookup by calculating the position from the key
- LRecommends the hash table, noting it does not support ordered or range queries
Linear search has time complexity O(n), so on 10 million records it would examine on average five million and at worst all ten million entries for every single query. It has the advantage of requiring no ordering or preparation at all, but at this scale and with frequent searching it is completely impractical. Binary search has complexity O(log n), which reduces the work to about 24 comparisons for ten million records, an improvement of roughly six orders of magnitude. Its precondition is that the data must be kept in sorted order, which means either sorting once at O(n log n) if the data is static, or paying an insertion cost to maintain the ordering as records are added, and inserting into a sorted array requires shifting subsequent elements. A hash table offers average O(1) lookup, because the hash function calculates the storage index directly from the key so no searching of any kind is performed, and the time taken does not increase as the number of records grows. Given that the search is by a unique key and is performed frequently, the hash table is the strongest choice, and it should be sized so the load factor stays low enough that collisions remain rare. The one caveat is that a hash table imposes no useful ordering on the data, so if the system also needs to retrieve records in key order or answer range queries such as all keys between two values, a balanced binary search tree giving O(log n) for both lookup and ordered traversal would be the better overall structure.