CS 2.3 Algorithms

What is time complexity, and what unit is it measured in?

A measure of how the number of instructions/operations an algorithm performs grows as the input size grows; it is measured in operations/steps, not in seconds or minutes, and is independent of the hardware running it

What is space complexity?

A measure of how much additional memory an algorithm requires to complete, relative to the size of its input

Why is an algorithm's time complexity independent of the CPU or hardware running it?

A faster CPU will complete each instruction more quickly, but it still has to carry out the same total number of instructions/steps as a slower CPU to solve the same problem — the algorithm's efficiency is about the number of steps, not the time each step takes

What is Big O notation used for?

Expressing how the complexity (scalability) of an algorithm grows as the size of its input increases, describing its "order" of growth

What are the two rules for simplifying an expression down to its Big O notation?

Remove all terms except the one with the largest factor or exponent (the dominant term), and remove any constants/coefficients

What does O(1) — constant time — mean?

The algorithm takes the same number of instructions to execute regardless of the size of the input data, e.g. finding the length of a string using a built-in length function

What does O(n) — linear time — mean, and what programming construct typically produces it?

The number of instructions grows proportionally with the input size (e.g. doubling the input roughly doubles the work); it's typically produced by a single loop that iterates once for each item in the input

What does O(n²) — polynomial/quadratic time — mean, and what programming construct typically produces it?

The number of instructions grows proportional to the square of the input size; it's typically produced by nested loops, where each loop iterates n times (e.g. a loop inside a loop)

*If a program contains three nested loops each iterating n times, what Big O time complexity would this produce?

O(n³) — each level of loop nesting adds another power to n, regardless of how many loops are nested; this is still classified as polynomial time

What does O(2^n) — exponential time — mean?

The number of instructions roughly doubles for every additional single input value added, causing the number of operations to become extremely large very quickly, even for modest input sizes

What does O(log n) — logarithmic time — mean, and what standard algorithm is a classic example?

The number of instructions grows very slowly even as the input size grows very large, because the algorithm can repeatedly discard a large fraction (e.g. half) of the remaining data at each step; a binary search is the classic example

From fastest (most efficient) to slowest (least efficient), order these Big O time complexities: O(n), O(1), O(n²), O(log n), O(2^n)

O(1) constant, then O(log n) logarithmic, then O(n) linear, then O(n²) polynomial, then O(2^n) exponential

*Simplify the expression 3n² + 4n + 5 to its Big O notation, and explain why

O(n²) — as n grows large, the n² term dominates and contributes far more to the total than the linear or constant terms, and coefficients (like the 3) are dropped since they contribute proportionally less as n increases

What is meant by an algorithm's best case, worst case, and average case complexity?

Best case is the most efficient possible outcome (e.g. finding the target on the first comparison); worst case is the least efficient possible outcome (e.g. never finding the target, or finding it last); average case is the typical outcome across all possible inputs

Why is Big O notation almost always quoted as the worst case complexity of an algorithm?

It gives programmers a guaranteed minimum/floor level of performance to expect, allowing them to reliably choose an appropriate algorithm for a problem regardless of how unlucky the specific input data turns out to be

What is a searching algorithm, and name the two standard ones covered at A-level

A method to find a specific value or element within a data structure; the two standard ones are linear search and binary search

How does a linear search work?

It searches a list sequentially from the start, comparing each element one at a time to the target value, until either the value is found or the end of the list is reached without a match

What precondition must be true for a binary search to work correctly, and why?

The list must already be sorted, because the algorithm relies on being able to eliminate half the remaining search space at each step based on whether the target is greater or less than the middle value — this logic breaks down on unordered data

How does a binary search work?

It compares the target to the middle item of the (sorted) list; if they match, it's found. If the target is smaller, the search continues on the lower half; if larger, it continues on the upper half; this repeats, halving the search space each time, until the item is found or the search space is empty

What is the time complexity of a linear search (best, worst, and average case)?

Best case O(1) (found immediately), worst case O(n) (found last, or not present), average case O(n) (proportional coefficients are removed, so O(n/2) simplifies to O(n))

What is the time complexity of a binary search (best, worst, and average case)?

Best case O(1) (found on first comparison at the midpoint), worst case O(log n), average case O(log n)

What is the space complexity of a linear search, and why?

O(1) — it only needs a constant amount of extra memory (e.g. a loop counter), regardless of how large the input list is

What is the space complexity of an iterative binary search, and why?

O(1) — it only uses a fixed number of variables (start, end, mid pointers) that don't grow as the input size increases

*Why would a linear search be preferred over a binary search on a small, unsorted list that is only searched once?

Sorting the list first (a prerequisite for binary search) would itself cost time, so for a single search on unsorted data, a linear search's O(n) with no sorting overhead is more efficient overall than sorting plus a binary search

How does a bubble sort work?

It repeatedly compares each pair of adjacent elements in the list and swaps them if they are in the wrong order; this process (a "pass") repeats until a full pass is completed with no swaps, at which point the list is sorted

What is the time complexity of a bubble sort (best, worst, and average case)?

Best case O(n) (already sorted list — one pass still needed to confirm no swaps), worst case O(n²) (reverse sorted list), average case O(n²)

What is the space complexity of a bubble sort, and why?

O(1) — it sorts in-place, only requiring a fixed amount of extra memory such as a loop counter and a temporary variable used during swaps

How does an insertion sort work?

It builds up a sorted section of the list one item at a time; each new item is compared to the items before it in the sorted section and inserted into its correct position, shifting larger items to the right to make space

What is the time complexity of an insertion sort (best, worst, and average case)?

Best case O(n) (already sorted list — each item only needs one comparison), worst case O(n²) (reverse sorted list), average case O(n²)

What is the space complexity of an insertion sort, and why?

O(1) — it sorts in-place and requires no additional memory that scales with the size of the input

How does a merge sort work? Describe its two main parts

Part one (divide): the list is repeatedly split in half until every sub-list contains only a single element. Part two (merge): pairs of sub-lists are repeatedly merged back together in sorted order until a single, fully sorted list remains

Why is merge sort described as a divide and conquer algorithm?

Because it works by dividing the problem into progressively smaller sub-problems (splitting the list) until each is trivially easy to solve (a single-element list), then combining (merging) the solved sub-problems back together into the full solution

What is the time complexity of a merge sort (best, worst, and average case)?

O(n log n) in all three cases — best, worst, and average — because regardless of the specific data, the same number of divide and merge operations must always be carried out

What is the space complexity of a merge sort, and why is it higher than a bubble or insertion sort?

O(n) — unlike bubble sort or insertion sort which sort in-place, merge sort requires additional memory to hold copies of the left and right halves of the list being merged at each step

How does a quick sort work?

A pivot value is chosen from the list; the list is partitioned into elements smaller than the pivot and elements larger than the pivot; each partition is then sorted recursively using the same process, until the whole list is sorted

What is the time complexity of a quick sort in the best and average case, and why?

O(n log n) — when the pivot roughly splits the list in half each time, there are approximately log n levels of recursion, and each level does n work to partition the list

What is the time complexity of a quick sort in the worst case, and what causes it?

O(n²) — this happens when the pivot is consistently chosen poorly (e.g. always the smallest or largest value, which can happen with already-sorted data), causing one partition to be empty each time and the recursion to degenerate into a single long chain

How can the worst-case scenario of quick sort typically be avoided in practice?

By using a randomised pivot selection or a "median-of-three" pivot selection strategy, rather than always picking a fixed position (like the first or last element), reducing the likelihood of consistently unbalanced partitions

What is the space complexity of a quick sort, and why?

O(n) — additional memory is required because copies of sub-lists are placed on the call stack during the recursive calls

*A programmer needs to sort a very large dataset and guarantee consistent performance regardless of the input order — would merge sort or quick sort be the safer choice, and why?

Merge sort, because its time complexity is O(n log n) in the best, worst, and average case, giving a guaranteed consistent performance; quick sort's worst case of O(n²) makes its performance less predictable, even though it's often faster in practice

What is Dijkstra's shortest path algorithm used for?

An optimisation algorithm that calculates the shortest path from a single starting node to every other node in a weighted graph

Describe the general process Dijkstra's algorithm follows

Set the start node's distance to 0 and all other nodes to infinity; repeatedly visit the unvisited node with the currently lowest known distance, and update the distance of each of its unvisited neighbours if a shorter path through the current node has been found; continue until all nodes have been visited

*Why does Dijkstra's algorithm always visit the unvisited node with the lowest current distance next, rather than any other order?

Because visiting nodes in increasing order of distance guarantees that by the time a node is visited, its shortest distance from the start has already been finalised — visiting a further node first could mean missing a shorter path that gets discovered later

Give two real-world examples of optimisation problems that Dijkstra's-style algorithms can solve

Any two of: finding the shortest route between two points (e.g. sat-nav journey planning), minimising resource usage in manufacturing, timetabling lessons/meetings, scheduling staff shifts

What is the A* search algorithm, and how does it improve on Dijkstra's algorithm?

A pathfinding algorithm that builds on Dijkstra's by adding a heuristic function to estimate the remaining distance to the goal, allowing it to prioritise exploring nodes that are likely closer to the goal, rather than exhaustively exploring in every direction like Dijkstra's does

In A* search, what do g(x) and h(x) represent?

g(x) is the real cost/distance travelled so far from the start node to the current node; h(x) is the heuristic — an estimate of the remaining distance from the current node to the goal node

What is f(x) in the A* search algorithm, and how is it calculated?

The total estimated cost of a path through a given node; it is calculated as f(x) = g(x) + h(x), combining the real distance so far with the estimated remaining distance

Why must the heuristic function h(x) used in A* never overestimate the real remaining cost to the goal?

If the heuristic overestimated the true distance, the algorithm could wrongly rule out a path that was actually optimal, since it would appear worse than it really is; underestimating (or being exactly accurate) ensures A* still finds the true shortest path

Why is A generally more efficient than Dijkstra's algorithm for finding a route to a single specific destination?

Dijkstra's exhaustively calculates the shortest distance from the start to every node in the graph, whereas A*'s heuristic actively guides its search toward the goal node, meaning it typically needs to explore far fewer nodes to find the specific path it's looking for