Comparing algorithms and ADTs in algorithms
| English | Chinese | Pinyin |
|---|---|---|
| Big-O | 大O表示法 | dà O biǎo shì fǎ |
| time complexity | 时间复杂度 | shí jiān fù zá dù |
| space complexity | 空间复杂度 | kōng jiān fù zá dù |
| depth-first | 深度优先 | shēn dù yōu xiān |
| breadth-first | 广度优先 | guǎng dù yōu xiān |
| binary tree | 二叉树 | èr chā shù |
The algorithm that would outlive the universe
- A salesman must visit 25 cities and return home by the shortest route. Try every order and there are about $10^{23}$ of them. A machine checking a billion a second would take three million years.
- Add one more city and the work multiplies by 25. That is not a computer that needs to be faster; it is an approach that can never work, at any speed, on any hardware.
- Knowing that before you write the program is what complexity analysis is for. It is the difference between choosing an algorithm and discovering, months later, that yours does not scale.
- This lesson is Big-O 大O表示法 for time and space, and how ADTs shape the algorithms built on them.
Time complexity
- Time complexity 时间复杂度 describes how the running time grows with the input size $n$. It is written in Big-O notation, which keeps only the dominant term and drops constants.
- $O(1)$ constant, the time does not depend on $n$ at all. $O(\log n)$ logarithmic, as in binary search. $O(n)$ linear, as in linear search. $O(n \log n)$, the good sorts. $O(n^2)$ quadratic, as in bubble and insertion sort.
- The reason constants are dropped: they are swamped. An $O(n^2)$ algorithm might beat an $O(n \log n)$ one for $n = 10$, but at $n = 10{,}000$ nothing about the constants can save it.
The curves cross once, and after that the order decides everything
How running time grows with n
Slide n upward and compare the curves: O(1) and O(log n) stay almost flat, O(n) rises steadily, O(n²) explodes. This is why Big-O — not a stopwatch — is how we compare algorithms on large inputs.
Which Big-O describes binary search?
Halving the range each step is logarithmic — O(log n).
Which Big-O describes bubble sort in the worst case?
Two nested loops over n elements give O(n²).
Match each algorithm to its time complexity.
Linear search is O(n), binary search O(log n), bubble sort O(n²).
Worked example: what doubling the input does
- An algorithm takes 4 seconds on 1,000 items. Estimate its time on 2,000 items if it is $O(n)$, then if it is $O(n^2)$.
- $O(n)$: doubling $n$ doubles the time, so about 8 seconds.
- $O(n^2)$: doubling $n$ quadruples the time, so about 16 seconds. At 10,000 items it would be 100 times the original, about 400 seconds.
- $O(\log n)$ would add only a single step, and $O(1)$ would not change at all. Reason from the order, not from a formula.
An O(n squared) algorithm takes 4 seconds on 1,000 items. Roughly how many seconds will it take on 2,000?
Doubling n quadruples an O(n squared) time. The same doubling would take an O(n) algorithm from 4 seconds to 8.
Space complexity
- Space complexity 空间复杂度 is the extra memory an algorithm needs, beyond the input itself.
- Bubble and insertion sort use $O(1)$ extra memory: they work in place, needing only a couple of variables. Merge sort uses $O(n)$, since it builds a second array.
- Recursion uses stack memory proportional to its depth, because every unfinished call keeps its own frame.
- There is often a time and memory trade-off: storing results to avoid recomputing them, as memoisation does, buys speed with space.
What else decides the choice
- Big-O is about growth, not absolute speed. For a small $n$, a simple $O(n^2)$ algorithm can beat a complicated $O(n \log n)$ one, and it is easier to write correctly.
- Stability matters when a list is already ordered by another field. Simplicity matters because a simple algorithm has fewer places to hide a bug.
- The honest answer to "which algorithm" often names the order and the conditions: this one, because $n$ is large and the data arrives unsorted.
An "in place" sort:
In-place algorithms (like bubble and insertion sort) sort within the original array, using constant extra space.
Why is bubble sort's space complexity O(1) even though it sorts an array of n items?
It sorts in place. Merge sort is O(n) because it builds a second array, and recursion costs memory proportional to its depth.
ADTs inside algorithms
- The abstract data types from topic 10 are the machinery algorithms are built from, and choosing one shapes the algorithm.
- A stack gives depth-first 深度优先 search: push the neighbours, take the most recent, and the search plunges down one path before backing up. Recursion uses the call stack for exactly this.
- A queue gives breadth-first 广度优先 search: enqueue the neighbours, take the oldest, and the search spreads outward in rings, which is what finds the shortest path in an unweighted graph.
- A binary tree 二叉树 keeps values in order so that a search discards half the remaining nodes at each step, giving binary search's $O(\log n)$ over a structure that can also grow.
Which statements about Big-O are correct? Select all that apply.
Big-O says nothing about seconds; it is about growth. That is why the crossover with a simpler algorithm exists at small sizes.
Worked example: the same graph, two searches
- A maze is explored from one entrance. Contrast using a stack with using a queue.
- With a stack, the most recently found path is explored next, so the search goes deep down one route until it dead-ends, then backtracks. It uses memory proportional to the depth of the path.
- With a queue, the oldest found path is explored next, so the search examines everything one step away, then everything two steps away. It finds the shortest route first, but holds every position at the current distance in memory.
- Name the ADT, name the resulting order of exploration, and name the consequence.
A stack (LIFO) naturally drives a depth-first traversal, while a queue (FIFO) drives a breadth-first traversal.
The ADT you choose decides the search order — stack goes deep first, queue explores level by level.
Match each ADT to the search it produces and its consequence.
Most recent first, or oldest first. That single choice decides whether the search goes deep or wide.
Marks that slip away
- Big-O describes growth with input size, not seconds. "It is fast" is not a complexity answer.
- Doubling the input doubles an $O(n)$ time and quadruples an $O(n^2)$ one. Reason from the order.
- Space complexity is the extra memory, which is why an in-place sort is $O(1)$ even though the array is size $n$.
- Stack gives depth-first, queue gives breadth-first. Getting that pair the right way round is the whole of several questions.
You've got it
- time complexity in Big-O describes growth with $n$: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$; constants are dropped because at scale the order decides
- doubling $n$ doubles $O(n)$ and quadruples $O(n^2)$; the crossover with a "worse" algorithm only exists for small $n$
- space complexity is the extra memory: in place sorts are $O(1)$, merge sort is $O(n)$, and recursion costs stack depth
- a stack gives depth-first search, a queue gives breadth-first, and a binary tree halves the remaining nodes at each step