Intuition The one-sentence ideaBig-O describes an upper bound on how fast a function grows, ignoring constant factors and small inputs . We say "f ( n ) f(n) f ( n ) O ( g ( n ) ) O(g(n)) O ( g ( n )) f f f no faster than g g g n n n
Intuition Why we throw away constantsSuppose Algorithm A runs in 5 n 5n 5 n 100 n 100n 100 n 5 5 5 100 100 100 doesn't change is the shape : both grow linearly . Big-O captures the shape, not the machine.
Likewise we ignore small n n n O ( n 2 ) O(n^2) O ( n 2 ) O ( n ) O(n) O ( n ) n = 3 n=3 n = 3 scaling , i.e. behaviour as n → ∞ n \to \infty n → ∞
So Big-O answers: "As input size explodes, roughly how does cost blow up?"
Definition Big-O (formal)Let f , g : N → R ≥ 0 f, g : \mathbb{N} \to \mathbb{R}^{\ge 0} f , g : N → R ≥ 0 f ( n ) = O ( g ( n ) ) f(n) = O(g(n)) f ( n ) = O ( g ( n )) = = c > 0 = = ==c > 0== == c > 0 == = = n 0 ≥ 0 = = ==n_0 \ge 0== == n 0 ≥ 0 == 0 ≤ f ( n ) ≤ c ⋅ g ( n ) for all n ≥ n 0 . 0 \le f(n) \le c \cdot g(n) \quad \text{for all } n \ge n_0. 0 ≤ f ( n ) ≤ c ⋅ g ( n ) for all n ≥ n 0 .
Read it aloud: "There is some multiplier c c c n 0 n_0 n 0 n 0 n_0 n 0 f f f c g c\,g c g
Three moving parts you MUST be able to recall:
c c c constant multiplier (absorbs hidden coefficients).n 0 n_0 n 0 threshold past which the bound holds (lets us ignore small-n n n The inequality is one-sided (≤ \le ≤ upper bound only.
The whole game is: pick a c c c n 0 n_0 n 0
3 n + 7 = O ( n ) 3n + 7 = O(n) 3 n + 7 = O ( n ) Goal: find c , n 0 c, n_0 c , n 0 3 n + 7 ≤ c n 3n + 7 \le c\,n 3 n + 7 ≤ c n n ≥ n 0 n \ge n_0 n ≥ n 0
Step 1 — bound the small term by the big term.
Why this step? For n ≥ 7 n \ge 7 n ≥ 7 7 ≤ n 7 \le n 7 ≤ n some threshold; 7 7 7 3 n + 7 ≤ 3 n + n = 4 n ( n ≥ 7 ) . 3n + 7 \le 3n + n = 4n \quad (n \ge 7). 3 n + 7 ≤ 3 n + n = 4 n ( n ≥ 7 ) . Why this step? The right side is now 4 ⋅ n = c g ( n ) 4 \cdot n = c\,g(n) 4 ⋅ n = c g ( n ) g ( n ) = n g(n)=n g ( n ) = n c = 4 c = 4 c = 4 n 0 = 7 n_0 = 7 n 0 = 7 ■ \blacksquare ■
(Many valid choices exist — e.g. c = 10 , n 0 = 1 c=10, n_0=1 c = 10 , n 0 = 1 one .)
2 n 2 + 3 n + 1 = O ( n 2 ) 2n^2 + 3n + 1 = O(n^2) 2 n 2 + 3 n + 1 = O ( n 2 ) Goal: 2 n 2 + 3 n + 1 ≤ c n 2 2n^2 + 3n + 1 \le c\,n^2 2 n 2 + 3 n + 1 ≤ c n 2 n ≥ n 0 n \ge n_0 n ≥ n 0
Step 1 — dominate each lower term by n 2 n^2 n 2 Why this step? For n ≥ 1 n \ge 1 n ≥ 1 3 n ≤ 3 n 2 3n \le 3n^2 3 n ≤ 3 n 2 1 ≤ n 2 1 \le n^2 1 ≤ n 2 2 n 2 + 3 n + 1 ≤ 2 n 2 + 3 n 2 + n 2 = 6 n 2 ( n ≥ 1 ) . 2n^2 + 3n + 1 \le 2n^2 + 3n^2 + n^2 = 6n^2 \quad (n \ge 1). 2 n 2 + 3 n + 1 ≤ 2 n 2 + 3 n 2 + n 2 = 6 n 2 ( n ≥ 1 ) . c = 6 c = 6 c = 6 n 0 = 1 n_0 = 1 n 0 = 1 ■ \blacksquare ■
Lesson: a degree-d d d O ( n d ) O(n^d) O ( n d )
f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f ( n ) = O ( g ( n )) f = n f=n f = n g = n 2 g=n^2 g = n 2 n ≥ 1 n \ge 1 n ≥ 1 n ≤ n 2 n \le n^2 n ≤ n 2 c = 1 , n 0 = 1 c=1, n_0=1 c = 1 , n 0 = 1 n = O ( n 2 ) n = O(n^2) n = O ( n 2 ) Why this matters: Big-O is an upper bound, so a function can be O O O strictly faster . n = O ( n 2 ) n = O(n^2) n = O ( n 2 ) loose (not tight).
n 2 ≠ O ( n ) n^2 \ne O(n) n 2 = O ( n ) Why this step? Suppose it were true: n 2 ≤ c n n^2 \le c\,n n 2 ≤ c n n ≥ n 0 n \ge n_0 n ≥ n 0 n > 0 n>0 n > 0 n ≤ c n \le c n ≤ c c c c fixed constant and n n n n > c n > c n > c ( c , n 0 ) (c,n_0) ( c , n 0 ) ■ \blacksquare ■ break a Big-O claim: derive a contradiction with n → ∞ n\to\infty n → ∞
Recall Forecast before reading the answerQ: Is 1000 n = O ( n ) 1000n = O(n) 1000 n = O ( n )
Verify: YES. Take c = 1000 , n 0 = 0 c = 1000, n_0 = 0 c = 1000 , n 0 = 0 1000 n ≤ 1000 ⋅ n 1000n \le 1000\cdot n 1000 n ≤ 1000 ⋅ n point of Big-O.
Recall ForecastQ: Is 2 n = O ( n 100 ) 2^{n} = O(n^{100}) 2 n = O ( n 100 )
Verify: NO. Any exponential eventually overtakes any polynomial: for large n n n 2 n / n 100 → ∞ 2^n / n^{100} \to \infty 2 n / n 100 → ∞ c c c
Common mistake "Big-O is theexact running time."
Why it feels right: we casually say "this is O ( n ) O(n) O ( n ) n n n The fix: Big-O is an upper bound , not equality. f = O ( g ) f = O(g) f = O ( g ) f f f slower . For exact/tight bounds use Θ \Theta Θ = = = f = O ( g ) f=O(g) f = O ( g ) f ∈ O ( g ) f \in O(g) f ∈ O ( g ) set membership .
Common mistake "I must keep constants and lower-order terms."Why it feels right: in real benchmarks the constant matters!
The fix: In the asymptotic world we deliberately drop them: 5 n 2 + 99 n + 7 = O ( n 2 ) 5n^2 + 99n + 7 = O(n^2) 5 n 2 + 99 n + 7 = O ( n 2 ) c c c
n 0 n_0 n 0 Why it feels right: seems like you should find the smallest threshold.
The fix: Any valid n 0 n_0 n 0
f = O ( g ) f=O(g) f = O ( g ) g = O ( f ) g=O(f) g = O ( f ) Why it feels right: symmetry intuition from = = = The fix: False — it's directional. n = O ( n 2 ) n = O(n^2) n = O ( n 2 ) n 2 ≠ O ( n ) n^2 \ne O(n) n 2 = O ( n ) ≤ \le ≤ = = =
Recall Explain to a 12-year-oldImagine you're timing how long it takes to hand out candy to a class. If there are n n n n n n "it grows like the number of kids." You don't care that one teacher is twice as fast (that's a constant), and you don't care about the tiny setup time. You only care: if the class doubles, the work roughly doubles. Big-O is the lazy-but-honest way to say how the work scales when things get huge.
"O for Over the top, after a while." O O O Over -estimate (upper bound), that holds after a while (past n 0 n_0 n 0 × c \times c × c
Big-O formal definition f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f ( n ) = O ( g ( n )) iff
∃ c > 0 , n 0 ≥ 0 \exists\, c>0, n_0\ge 0 ∃ c > 0 , n 0 ≥ 0 such that
0 ≤ f ( n ) ≤ c g ( n ) 0\le f(n)\le c\,g(n) 0 ≤ f ( n ) ≤ c g ( n ) for all
n ≥ n 0 n\ge n_0 n ≥ n 0 .
What does the constant c c c Hidden coefficients / constant factors, so machine- and implementation-dependent multipliers are ignored.
What is the role of n 0 n_0 n 0 A threshold; the bound only needs to hold for sufficiently large
n n n , ignoring small-input behaviour.
Is Big-O an upper or lower bound? Upper bound only (the inequality is one-sided
≤ \le ≤ ). For lower use
Ω \Omega Ω , for tight use
Θ \Theta Θ .
Prove 3 n + 7 = O ( n ) 3n+7=O(n) 3 n + 7 = O ( n ) For
n ≥ 7 n\ge 7 n ≥ 7 ,
3 n + 7 ≤ 3 n + n = 4 n 3n+7\le 3n+n=4n 3 n + 7 ≤ 3 n + n = 4 n , so
c = 4 , n 0 = 7 c=4, n_0=7 c = 4 , n 0 = 7 .
Why is n 2 ≠ O ( n ) n^2 \ne O(n) n 2 = O ( n ) Would require
n ≤ c n\le c n ≤ c for all large
n n n , contradicting
n → ∞ n\to\infty n → ∞ with fixed
c c c .
Sum rule for Big-O O ( f ) + O ( g ) = O ( max ( f , g ) ) O(f)+O(g)=O(\max(f,g)) O ( f ) + O ( g ) = O ( max ( f , g )) ; the dominant term wins.
Is 2 n = O ( n 100 ) 2^n = O(n^{100}) 2 n = O ( n 100 ) No; exponentials eventually dominate any polynomial.
Does f = O ( g ) f=O(g) f = O ( g ) g = O ( f ) g=O(f) g = O ( f ) No, Big-O is directional (like
≤ \le ≤ ), not symmetric.
True or false: a degree-d d d O ( n d ) O(n^d) O ( n d ) True; bound every lower power by
n d n^d n d .
Behaviour as n to infinity
Polynomial is O of top power
Intuition Hinglish mein samjhoBig-O ka matlab simple hai: ye batata hai ki tumhara algorithm input bada hone par kitni tezi se slow hota hai — exact time nahi, balki growth ki shape . Formal definition yaad rakho: f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f ( n ) = O ( g ( n )) c > 0 c>0 c > 0 n 0 n_0 n 0 n ≥ n 0 n\ge n_0 n ≥ n 0 f ( n ) ≤ c ⋅ g ( n ) f(n)\le c\cdot g(n) f ( n ) ≤ c ⋅ g ( n ) c c c n 0 n_0 n 0
Proof karne ka tarika ekdam mechanical hai: ek c c c n 0 n_0 n 0 3 n + 7 3n+7 3 n + 7 n ≥ 7 n\ge 7 n ≥ 7 7 ≤ n 7\le n 7 ≤ n 3 n + 7 ≤ 4 n 3n+7\le 4n 3 n + 7 ≤ 4 n c = 4 , n 0 = 7 c=4, n_0=7 c = 4 , n 0 = 7 2 n 2 + 3 n + 1 ≤ 6 n 2 2n^2+3n+1\le 6n^2 2 n 2 + 3 n + 1 ≤ 6 n 2
Sabse important baat: Big-O sirf upper bound hai, exact value nahi. Isliye n = O ( n 2 ) n=O(n^2) n = O ( n 2 ) one-directional hai — n = O ( n 2 ) n=O(n^2) n = O ( n 2 ) n 2 = O ( n ) n^2=O(n) n 2 = O ( n ) n n n c c c c c c
