Algorithm & Algorithm Analysis
dsa.fetehadin.com2.1 Algorithms & Their Properties
An algorithm is a finite, unambiguous sequence of steps that solves a problem. Learn the 11 properties every correct algorithm must have.
| findMax: comparisons | exactly n − 1 |
| findMax: time | O(n), and best = worst |
| Space | O(1) |
- ✗Confusing definiteness (each step has one clear meaning) with finiteness (the algorithm stops).
- ✗Saying an algorithm needs at least one input. It needs zero or more inputs but at least one output.
- ✗Treating "a program" and "an algorithm" as the same. A program may run forever (an OS); an algorithm must terminate.
2.2 Measuring Efficiency
Empirical vs theoretical analysis, qualitative vs quantitative, the three classic avoidable inefficiencies, and the time–space trade-off.
| Search with late termination | always n checks |
| Search that breaks early | 1 … n checks |
| Duplicate check with nested loops | O(n²) time, O(1) space |
| Duplicate check with a set | O(n) time, O(n) space ← trade-off |
- ✗Saying empirical analysis is useless. It is useful, but its results depend on the machine, compiler, language and inputs.
- ✗Mixing up "redundant computation" (recomputing the same value in a loop) with "repeated array referencing" (reading
a[i]many times). - ✗Thinking the faster algorithm is always better. It may need far more memory.
2.3 Counting Time Units
Turn code into a formula T(n) using the instructor's counting rules. Loops become sums, and nested loops multiply.
Single loop for(i=0;i<n;i++) k=k+1; cout<<k; | T(n) = 4n + 3 → O(n) |
Nested n × n loop with k++ | T(n) = 3n² + 4n + 3 → O(n²) |
Loop where i doubles (i *= 2) | ≈ log₂ n iterations → O(log n) |
- ✗Counting the loop test n times instead of n + 1 (the last, failing test counts too).
- ✗Counting
k = k + 1as 1 unit. It is 2: one addition and one assignment. - ✗For
if/else, adding both branches. Count the condition plus the larger branch only.
2.4 Best, Average & Worst Case
The same algorithm can be fast or slow depending on the input. We analyse the best, average and worst case, and usually report the worst.
| Linear search: best (key is first) | O(1): 1 comparison |
| Linear search: average (key present) | (n + 1) / 2 comparisons → O(n) |
| Linear search: worst (last or missing) | n comparisons → O(n) |
| Bubble sort with flag: best / worst | O(n) / O(n²) |
| Space | O(1) |
- ✗"Best case is when n is small." No: best case is about the arrangement of the input for a given n, never about a small n.
- ✗Thinking the average case is (best + worst) / 2. It is an expected value over all inputs.
- ✗Mixing up the case with the notation. "Worst case" is not the same thing as "Big-O".
2.5 Asymptotic Notation & Big-O Proofs
O, Ω, Θ, o and ω describe how fast T(n) grows for large n. Learn the definitions, the order of growth, and how to prove f(n) = O(g(n)) by finding c and k.
| O(1) | constant: array access, push/pop |
| O(log n) | logarithmic: binary search |
| O(n) | linear: linear search, traversal |
| O(n log n) | linearithmic: merge sort, heap sort |
| O(n²) | quadratic: bubble, selection, insertion sort |
| O(n³) | cubic: three nested loops |
| O(2ⁿ) | exponential: all subsets, naive Fibonacci |
- ✗Forgetting to state c and k explicitly. A proof without numbers gets partial marks.
- ✗Claiming 3n² = O(n). False: no constant c makes 3n² ≤ c·n for all large n.
- ✗Thinking Big-O means "worst case". Big-O is an upper bound on a function; you can give an upper bound for the best case too.
- Algorithm:
- A finite, well-defined sequence of steps that turns input into the desired output.
- Finiteness:
- An algorithm must stop after a finite number of steps.
- Definiteness:
- Every step is precise and unambiguous.
- Empirical analysis:
- Measuring an algorithm by running it and timing it. Depends on the machine and the input.
- Theoretical analysis:
- Counting basic operations as a function of input size n. Machine-independent.
- Time unit:
- One basic operation (assignment, single I/O, Boolean or arithmetic op, return) counted as 1 in T(n).
- T(n):
- The running time of an algorithm as a function of input size n, in time units.
- Best / average / worst case:
- The running time on the most favourable, typical, and least favourable input of size n.
- Big-O (O):
- Upper bound: f(n) = O(g(n)) if f(n) ≤ c·g(n) for all n ≥ k, for some constants c > 0 and k.
- Big-Omega (Ω):
- Lower bound: f(n) ≥ c·g(n) for all n ≥ k.
- Big-Theta (Θ):
- Tight bound: f(n) is both O(g(n)) and Ω(g(n)).
- Little-o / little-omega:
- Strict bounds: f grows strictly slower (o) or strictly faster (ω) than g.
- Time/space trade-off:
- Using more memory to save time (or the reverse), e.g. storing results instead of recomputing them.