| ISSUE 11/30 · COMPUTER SCIENCE |
~3 MIN |
FOUNDATION / ALGORITHMS · WEEK 02 — MACHINES UNDER PRESSURE
Big O is a growth warning
START HERE
Sorting ten photos is easy. Sorting ten million can overwhelm the same app, even when every photo looks ordinary. Big O is a shorthand programmers use to describe how the amount of work grows when the amount of input grows. It warns when doubling the number of items may double the work, quadruple it, or do something in between.
|
/ WHY NOW
An app sorts 1,000 photos instantly, so the code looks finished. Then a user imports 100,000 and the screen freezes. The machine did not suddenly get worse; the amount of work grew faster than the collection. Big O notation gives an upper bound: a ceiling on how quickly that work can grow for large inputs, while deliberately leaving out constants and smaller terms.
|
/ THE IDEA
Formally, O(n) says work is eventually bounded by a constant times n. Programmers often use it casually for proportional growth, more precisely written Θ(n). O(n²) allows quadratic growth; O(n log n), common for good comparison sorting, sits between them. Big O is not a stopwatch result. It is a forecast of how an algorithm’s dominant work changes as n becomes large.
THE FORMAL IDEA
work(n): n | n log₂n | n²
| n = number of input items | | log₂n = how many times n can be halved before reaching 1 | | constants and small setup costs are deliberately hidden |
|
RUN THE TINY EXAMPLE
Double a photo collection
Toy dominant-work units, 8 → 16 photos: n goes 8 → 16 (2×) n log₂n goes 24 → 64 (about 2.7×) quadratic work goes 64 → 256 (4×)
|
Keep doubling and the quadratic gap becomes enormous. That is why a better algorithm on modest hardware can beat a poor one on a faster machine.
/ SO WHAT?
Whenever a product must handle ten or a thousand times more users, files or records, ask how the work scales. Reducing a fixed cost helps today; changing how quickly work grows can rescue the future.
ONE CAVEAT |
| Big O hides constants, hardware, cache behaviour and typical inputs. For small data, an algorithm with worse theoretical growth can still be faster and simpler. |
KEEP THIS
Big O tells you how speed changes when the problem grows—not how many seconds one run takes.
|
NEXT: The LHC is going dark to get brighter
|