Big-O Notation — Brief ☧
Deep version → | Lab → | Flashcards →
Q: A priest must bless each of the twelve tribes of Israel.
How does the time grow if there are more tribes?
A: One blessing per tribe. Twice the tribes, twice the time. That is O(N) — linear.
Q: Now each tribe must greet every other tribe at a feast.
How does the time grow?
A: Each of 12 tribes greets 11 others = 132 greetings. If 24 tribes: 24 x 23 = 552.
Doubling the tribes quadruples the greetings. That is O(N squared) — quadratic.
Q: A scribe keeps the names of all the people on a scroll, written
in the order of their Hebrew names — aleph (א) first, then bet (ב),
and so on. In the margin, he marks where each letter begins: "Names
starting with gimel (ג) begin here." If someone asks "Is Gad (גָּד) in
the scroll?", how does the scribe find him?
A: He turns to the gimel (ג) section using the margin index, then
searches within that section. But he can do better: open the scroll
to the middle. Is Gad before or after? Discard the wrong half. Repeat.
Each step cuts the possibilities in half. That is O(log N) —
logarithmic. For 1,000 names, only about 10 steps.
Q: Could the scribe do even better than halving each time?
A: Yes — if every person's name could be turned into a unique number.
Imagine a rule: take the letters of "יְהוּדָה" (Yehudah), and by some
calculation — adding their values, multiplying, shifting — you get a
number: position 7. "דָּן" (Dan) gives position 5. Every name has its own
computed address.
To find anyone, compute their number and go directly there. No
searching at all. That is a hash table — O(1),
constant. It does not grow with the scroll's length.
Q: But what if two names give the same number?
A: That is a collision. You keep a short
list at that position, or look at the next empty spot. A good
hash function makes collisions rare.
The Scale
| Big-O | Name | 12 tribes | 1,000 tribes | Example |
|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | Hash lookup, bitwise AND |
| O(log N) | Logarithmic | 4 | 10 | Binary search in a sorted scroll |
| O(N) | Linear | 12 | 1,000 | Scan a list, bless each tribe |
| O(N log N) | Linearithmic | 43 | 10,000 | Sort the genealogies |
| O(N squared) | Quadratic | 144 | 1,000,000 | All pairs greet each other |
| O(2^N) | Exponential | 4,096 | 10^301 | Brute-force SAT |
Your FPGA's inner loop is O(1) — one AND per clock cycle, regardless of domain size
(within a 64-bit word). That is why it outperforms solvers that are O(N) or worse.
Soli Deo Gloria