Why complexity first
Before implementation details, we need a growth model. Asymptotic analysis
captures how running cost scales with input size n, which is often more
important than constant-factor micro-optimizations.
Cost model and Big-O
Definition
Asymptotic upper bound (Big-O)
means there exist constants and such that for all .
This definition is a proof obligation: you must show constants and a valid threshold, not only say “it looks quadratic”.
Typical growth classes in CSCI2520
O(1): direct index access, pointer re-link (with known node addresses).O(log n): balanced-tree search, binary-search style halving.O(n): full scan in array/list.O(n log n): merge/heap style divide + linear merge phase.- : nested scan (e.g. simple comparison-based double loops).
Read and try
Compare asymptotic growth at one n
Compares growth classes at the same n so relative scaling becomes concrete.
| Class | Value at n=16 |
|---|---|
| O(1) | 1.00 |
| O(log n) | 4.00 |
| O(n) | 16.00 |
| O(n log n) | 64.00 |
| O(n^2) | 256.00 |
Worked comparison
Worked example
When does n log n dominate n?
For , and , so n log n is already larger.
As n grows, n log n stays asymptotically below but above linear.
Quick checks
Quick check
If an algorithm has two nested loops each running n times, what class is the total cost?
Assume loop body is O(1).
Solution
Answer
Quick check
Why does O(n log n) beat O(n^2) for sufficiently large n?
Compare ratio (n^2)/(n log n).
Solution