Intuition The one core ideaBig-O is a way to compare how two functions grow when their input gets huge, while deliberately ignoring constant multipliers and small inputs. Everything on the parent page is machinery for making one sentence precise: "f g
This page assumes nothing . Every squiggle on the parent note — f g N ≤ → ∞ ∃
A function is a machine: you feed it one number in, it spits one number out. We write f ( n ) f n
The picture: a box with an arrow going in (labelled n f ( n )
In complexity analysis the input n size of the problem (how many items to sort, how long the list is) and the output f ( n ) cost (how many steps the algorithm takes). So f "how much work for a problem of size n
Intuition Why we draw functions as dots, not a solid curveA single number f ( 50 ) scaling — what happens across all input sizes. So we plot n f ( n ) n counting number (Section 1), so f ( n ) n = 0 , 1 , 2 , 3 , … isolated dots , not at every real point in between. There is no such thing as "f ( 3.5 ) n draw a smooth line through the dots just to make the trend visible to the eye — but that line is a reading aid, not part of the function. Keep the dots in mind: the growth "shape" is the pattern those dots trace as they march rightward.
N N 0 , 1 , 2 , 3 , …
Input sizes are counting numbers — you can have a list of 0 7 3.5 f : N → … the input lives in N This is exactly why the graph in Section 0 is a set of dots , not a continuous curve — the domain has gaps.
R ≥ 0 R ≥ 0 at or right of zero : 0 , 0.5 , 1 , π , 1000 , …
Cost is never negative (an algorithm can't take − 3 R ≥ 0
→ f : N → R ≥ 0 f : A → B f A B asymmetry : inputs are discrete dots (N R ≥ 0
→ Why it feels right: you'll soon meet n → ∞ does mean "approaches."
The fix: the arrow has two jobs . In f : N → R ≥ 0 n → ∞ n
Definition Less-than-or-equal,≤ a ≤ b a b a left of b
For two curves, f ( n ) ≤ g ( n ) at a single input n f g at that horizontal position . Big-O will ask for this "f g every input dot past a threshold — that is the heart of the definition.
Intuition Why one-sided (≤ = f ( n ) = g ( n ) exactly — impossibly strict, and machine-dependent. Demanding only f ( n ) ≤ c g ( n ) "does f g Big-O is an upper bound precisely because its inequality points one way.
A constant is a number that does not change as n n variable : it takes every value 0 , 1 , 2 , …
Definition The multiplierc c real constant with c > 0 c ∈ R + c 4 0.5 3 7 not be a whole number). We multiply the whole g c g ( n ) g stretched vertically by factor c
The picture: take the g c = 2 f 100 g same shape , we pick c = 100 f c g
c > 0 c ≤ 0 c = 0 c g ( n ) = 0 c < 0 positive real stretch makes sense.
Common mistake "The bound works even if the yardstickg ( n ) Why it feels right: we rarely check g The fix: for c g ( n ) bound a positive cost, we implicitly need g ( n ) > 0 n ≥ n 0 g ( n ⋆ ) = 0 c g ( n ⋆ ) = 0 f ( n ⋆ ) f ≤ c g n n 2 log n n ≥ 2 2 n strictly positive once n n 0 g
n 0 n 0 starting line . We only care about what happens for inputs n ≥ n 0 n 0
The picture: draw a vertical line at n 0 right of that line is the region Big-O looks at; everything left of it (the small inputs) is crossed out.
Intuition Why we throw away small inputsFor tiny n O ( n 2 ) O ( n ) n = 3 scaling . By starting at n 0 n 0 ≥ 1 n = 0 n
n 0 Why it feels right: it feels tidy to find the exact crossover point.
The fix: any threshold that works proves the claim. The definition asks whether some n 0 n 0 ≥ 1 n
The parent's definition says: "there exist constants c , n 0 n ≥ n 0 … Two logic words, two jobs.
∃ ∃ c find at least one value of c
∀ n ≥ n 0 every single input past the threshold must obey the inequality — no exceptions allowed."
Intuition Why the order matters: findc , n 0 n "there exist c ∈ R + n 0 n . This means: you lock in one c one n 0 up front , and then that single pair must handle every large n c n n 2 = O ( n ) c
n → ∞ n n Crucially, ∞ — you cannot plug it in as "f ( ∞ ) process : "pick any bound you like, and n n Limits and infinity (Calculus) ; for now hold the intuition — "no matter how big a wall you build, n
f g n f g g precise we look at the ratio g ( n ) f ( n ) g ( n ) > 0 n → ∞ lim n → ∞ g ( n ) f ( n ) = ∞ ⟺ f grows strictly faster than g . finite number, f g f ∈ O ( g )
The picture: two sets of dots both climbing, but the steeper one pulling away and never being caught. That "never caught even after stretching" is the ratio racing to ∞
Intuition Why "faster" and "O f ∈ O ( g ) f no faster than g g bounded , so a single constant stretch c g f strictly faster (g f → ∞ c f ∈ / O ( g ) n 2 ∈ / O ( n ) n n 2 = n → ∞
Now every piece is earned, so the parent's definition becomes plain English.
f = O ( g ) Why it feels right: the "= The fix: O ( g ) set — the collection of all functions that grow no faster than g f ∈ O ( g ) f f = O ( g ) abuse of notation we tolerate for brevity; it does not mean f O ( g ) = f f ∈ O ( g )
Worked example Watch the machinery run: is3 n + 7 ∈ O ( n )
f ( n ) = 3 n + 7 g ( n ) = n n ≥ 1 Pick c = 4 ∈ R + n 0 = 7
For every n ≥ 7 7 ≤ n 3 n + 7 ≤ 3 n + n = 4 n = c g ( n )
We found one pair (∃ all large n 3 n + 7 ∈ O ( n )
Worked example Watch it FAIL: isn 2 ∈ O ( n ) c n 0 First insist n 0 ≥ 1 so that every n ≥ n 0 n > 0 n 2 ≤ c n n dividing by n > 0 (safe precisely because n 0 ≥ 1 n ≤ c n → ∞ c frozen (Section 3) — once n > c n n 2 = n → ∞ c c n n 2 ∈ / O ( n )
Test yourself — cover the right side and answer before revealing.
What is a function f ( n ) A machine taking input size n
Why is the graph of f ( n ) The domain is N 0 , 1 , 2 , … f
What set do input sizes n N 0 , 1 , 2 , …
What set do costs f ( n ) R ≥ 0
What type of number is the constant c A positive real , c ∈ R +
What does f ( n ) ≤ c g ( n ) The f g c
Why must c > 0 A zero or negative stretch could never sit above a positive cost curve.
Why do we implicitly need g ( n ) > 0 n 0 If g ( n ) = 0 c g ( n ) = 0 f ( n )
What does the threshold n 0 The messy small-input region where dots cross unpredictably; we study only n ≥ n 0 n 0 ≥ 1 n
Does n 0 No — any working n 0
What does ∃ c , n 0 Find just one pair ( c , n 0 )
What does "for all n ≥ n 0 The inequality must hold at every input past the threshold, no exceptions.
Why can c n You fix c c n
Why is "f = O ( g ) O ( g ) set of functions; the precise statement is the membership f ∈ O ( g ) =
Is ∞ No — ∞ process "n f ( ∞ )
How do you make "f g The ratio test: lim n → ∞ f ( n ) / g ( n ) = ∞ f f ∈ / O ( g )
3.1.01 Big-O notation — formal definition, mathematical (Hinglish) Big-Omega notation — lower bound Big-Theta notation — tight bound Little-o and little-omega Time Complexity vs Space Complexity Asymptotic growth rates ordering Master Theorem Limits and infinity (Calculus) 
