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ù |
Which algorithm is faster?
- How do we say one algorithm is "better" than another?
- Big-O 大O表示法 describes how the running time grows with the input size.
- We also weigh memory, stability and simplicity.
Time complexity 时间复杂度 (Big-O)
- Time complexity is how the running time grows with input size $n$, written in Big-O (the dominant term):
- $O(1)$ constant · $O(\log n)$ binary search · $O(n)$ linear search · $O(n \log n)$ good sorts · $O(n^2)$ bubble/insertion sort.
- A smaller order is better at scale, even if another algorithm is faster for tiny $n$.
Big-O growth curves: constant and logarithmic stay flat while quadratic shoots up as n grows
Binary search halves the range each step until W is found
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²).
Space complexity 空间复杂度 and other criteria
- Space complexity is the extra memory needed: bubble/insertion sort use $O(1)$ extra (in place); merge sort uses $O(n)$; recursion uses stack memory proportional to its depth.
- There's often a time–memory trade-off.
- Also consider simplicity, stability, and adaptiveness (faster on nearly-sorted data).
An "in place" sort:
In-place algorithms (like bubble and insertion sort) sort within the original array, using constant extra space.
ADTs inside algorithms
- The ADTs from data structures appear inside many algorithms:
- a stack drives depth-first 深度优先 traversal and undo; a queue drives breadth-first 广度优先 traversal.
- ADTs can be built from other ADTs (a queue from two stacks; a stack from a linked list; a binary tree 二叉树 from nodes with two child pointers) — layering separates concerns.
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.
You've got it
- Big-O ranks growth: $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2)$
- space complexity = extra memory; in place = $O(1)$ extra
- also weigh stability, simplicity, adaptiveness — and the time–memory trade-off
- stack → DFS, queue → BFS; ADTs can be built from other ADTs