Algorithms Reference
Algorithms and Complexity
An algorithm is a finite procedure for solving a class of problems; complexity describes how its work grows with the input size.
Solved Examples
Jump directly to a worked example by type.
Fact Table
| Idea | Meaning | Use or Check |
|---|---|---|
| Algorithm | A finite, unambiguous sequence of steps that produces the required result. | It must stop for every valid input. |
| Input size $n$ | A measure of how much data the procedure receives. | State what is being counted. |
| Big-O | $f(n)=O(g(n))$ means $g$ eventually bounds $f$ up to a constant factor. | It describes an upper growth rate, not an exact step count. |
| Linear search | Checks items one at a time until a match is found or the list ends. | Worst-case work grows proportionally to $n$. |
| Binary search | Repeatedly halves a sorted search interval. | It needs sorted input and grows logarithmically. |
Content Formulas
Constant
$$O(1)$$
Logarithmic
$$O(\log n)$$
Linear
$$O(n)$$
Quadratic
$$O(n^2)$$
Big-O ignores constant factors and lower-order terms when describing long-run growth. The input assumptions matter: binary search is not valid on an unsorted list.
Classic Examples
Trace a Linear Search
Search for 9 in the list $[4,7,9,12]$ using linear search.
Solution Steps
- Compare the target with entries from left to right.
- Stop when the target is found.
$$4\ne9\quad\text{(comparison 1)}$$
$$7\ne9\quad\text{(comparison 2)}$$
$$9=9\quad\text{(comparison 3)}$$
The target is at position 3; a list of length $n$ needs at most $n$ comparisons.
Count Binary Search Halvings
A sorted list has 64 entries. How many halvings reduce the search interval to one entry?
Solution Steps
- Write the interval sizes after each halving.
- Find $k$ such that $64/2^k=1$.
$$\frac{64}{2^k}=1\quad\Longrightarrow\quad2^k=64$$
$$k=6$$
The interval is reduced to one entry after 6 halvings.
Compare Growth Rates
Compare the dominant work for two procedures with $n=100$: one takes $n$ steps and the other takes $n^2$ steps.
Solution Steps
- Substitute $100$ for $n$.
- Compare the resulting step counts.
$$n=100\text{ steps}$$
$$n^2=10{,}000\text{ steps}$$
The quadratic procedure grows much faster as input size increases.