Intuition The one-sentence pictureIf O O O no slower than this," then Ω \Omega Ω no faster than this," and Θ \Theta Θ both agree — the growth is trapped between two copies of the same function.
Big-O O O promise of a ceiling . Saying "this sort is O ( n 2 ) O(n^2) O ( n 2 ) O ( n ) O(n) O ( n ) also O ( n 2 ) O(n^2) O ( n 2 ) O O O loose . To say "this growth is exactly n 2 n^2 n 2 floor (Ω \Omega Ω O O O tight bound Θ \Theta Θ
So the family is:
O O O Ω \Omega Ω Θ \Theta Θ
We compare functions f ( n ) f(n) f ( n ) g ( n ) g(n) g ( n ) n n n n 2 n^2 n 2 n log n n\log n n log n as n → ∞ n\to\infty n → ∞ . We don't care about small n n n shape of growth .
We want "f f f g g g after some point , f f f scaled copy of g g g
f ( n ) = O ( g ( n ) ) ⟺ ∃ c > 0 , n 0 > 0 : 0 ≤ f ( n ) ≤ c g ( n ) ∀ n ≥ n 0 f(n) = O(g(n)) \iff \exists\, c>0,\ n_0>0 \ :\ 0 \le f(n) \le c\,g(n)\quad \forall n\ge n_0 f ( n ) = O ( g ( n )) ⟺ ∃ c > 0 , n 0 > 0 : 0 ≤ f ( n ) ≤ c g ( n ) ∀ n ≥ n 0
Intuition WHY the constantc c c n 0 n_0 n 0 c c c constant factors (a 2× slower machine shouldn't change the class). n 0 n_0 n 0 small-n n n (startup overheads, a slow first iteration). We only judge the eventual trend.
"f f f no slower than g g g
Ω \Omega Ω f ( n ) = Ω ( g ( n ) ) ⟺ ∃ c > 0 , n 0 > 0 : 0 ≤ = = c g ( n ) ≤ f ( n ) = = ∀ n ≥ n 0 f(n)=\Omega(g(n)) \iff \exists\, c>0,\ n_0>0\ :\ 0 \le ==c\,g(n) \le f(n)== \quad \forall n\ge n_0 f ( n ) = Ω ( g ( n )) ⟺ ∃ c > 0 , n 0 > 0 : 0 ≤== c g ( n ) ≤ f ( n ) == ∀ n ≥ n 0 f f f above a scaled copy of g g g g g g floor on f f f
If g g g both a ceiling and a floor (with possibly different constants), the growth is pinned:
Θ \Theta Θ f ( n ) = Θ ( g ( n ) ) ⟺ ∃ c 1 , c 2 > 0 , n 0 > 0 : = = 0 ≤ c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n ) = = ∀ n ≥ n 0 f(n)=\Theta(g(n)) \iff \exists\, c_1,c_2>0,\ n_0>0\ :\ ==0 \le c_1 g(n) \le f(n) \le c_2 g(n)== \quad \forall n\ge n_0 f ( n ) = Θ ( g ( n )) ⟺ ∃ c 1 , c 2 > 0 , n 0 > 0 : == 0 ≤ c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n ) == ∀ n ≥ n 0 f = Θ ( g ) ⟺ f = O ( g ) AND f = Ω ( g ) f=\Theta(g) \iff f=O(g)\ \text{AND}\ f=\Omega(g) f = Θ ( g ) ⟺ f = O ( g ) AND f = Ω ( g )
3 n 2 + 5 n + 7 = Θ ( n 2 ) 3n^2+5n+7 = \Theta(n^2) 3 n 2 + 5 n + 7 = Θ ( n 2 ) Upper: for n ≥ 1 n\ge 1 n ≥ 1 3 n 2 + 5 n + 7 ≤ 3 n 2 + 5 n 2 + 7 n 2 = 15 n 2 3n^2+5n+7 \le 3n^2+5n^2+7n^2 = 15n^2 3 n 2 + 5 n + 7 ≤ 3 n 2 + 5 n 2 + 7 n 2 = 15 n 2 c 2 = 15 c_2=15 c 2 = 15 Why this step? We replaced lower-order terms 5 n , 7 5n,7 5 n , 7 n 2 n^2 n 2 ≤ \le ≤ Lower: 3 n 2 + 5 n + 7 ≥ 3 n 2 3n^2+5n+7 \ge 3n^2 3 n 2 + 5 n + 7 ≥ 3 n 2 n ≥ 0 n\ge 0 n ≥ 0 c 1 = 3 c_1=3 c 1 = 3 Why? Dropping positive terms only shrinks the expression, giving a clean floor.
Conclude: 3 n 2 ≤ f ( n ) ≤ 15 n 2 3n^2 \le f(n)\le 15n^2 3 n 2 ≤ f ( n ) ≤ 15 n 2 n ≥ 1 n\ge1 n ≥ 1 f = Θ ( n 2 ) f=\Theta(n^2) f = Θ ( n 2 ) c 1 = 3 , c 2 = 15 , n 0 = 1 c_1=3,c_2=15,n_0=1 c 1 = 3 , c 2 = 15 , n 0 = 1
n 2 ≠ O ( n ) n^2 \ne O(n) n 2 = O ( n ) n 2 = Ω ( n ) n^2=\Omega(n) n 2 = Ω ( n ) not Θ ( n ) \Theta(n) Θ ( n ) n 2 ≤ c n n^2\le c\,n n 2 ≤ c n n > 0 n>0 n > 0 n ≤ c n\le c n ≤ c Why this step? For it to hold for all large n n n c c c n n n O ( n ) O(n) O ( n ) n 2 ≥ 1 ⋅ n n^2\ge 1\cdot n n 2 ≥ 1 ⋅ n n ≥ 1 n\ge1 n ≥ 1 n 2 = Ω ( n ) n^2=\Omega(n) n 2 = Ω ( n ) not tight . ∎
Worked example 3) Lower bound of a problem vs an algorithmComparison-based sorting needs Ω ( n log n ) \Omega(n\log n) Ω ( n log n ) every possible algorithm for the problem (proved via the decision-tree height log 2 ( n ! ) = Θ ( n log n ) \log_2(n!)=\Theta(n\log n) log 2 ( n !) = Θ ( n log n ) O ( n log n ) O(n\log n) O ( n log n ) optimal : Θ ( n log n ) \Theta(n\log n) Θ ( n log n ) Why this matters: Ω \Omega Ω problem tells you no cleverness can do better.
Ω \Omega Ω Why it feels right: "lower" sounds like "fastest/easiest input." The truth: O , Ω , Θ O,\Omega,\Theta O , Ω , Θ T ( n ) T(n) T ( n ) best/worst/average is a separate axis (which input you picked). You can say "worst-case time is Ω ( n log n ) \Omega(n\log n) Ω ( n log n ) lower bound on the worst case . Fix: decide (1) which case you analyze, then (2) bound that case's function with O O O Ω \Omega Ω Θ \Theta Θ
O O O Ω \Omega Ω Why it feels right: worst is "highest," best is "lowest," matching the words. Fix: Same as above — bound symbols ≠ case selection. An algorithm can be Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) and Θ ( n ) \Theta(n) Θ ( n )
Common mistake "Every algorithm has aΘ \Theta Θ Why it feels right: functions usually have a clean shape. The truth: if best and worst differ in order , no single Θ \Theta Θ Θ ( n ) \Theta(n) Θ ( n ) Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) O ( n 2 ) O(n^2) O ( n 2 ) Ω ( n ) \Omega(n) Ω ( n ) not Θ \Theta Θ Fix: state Θ \Theta Θ O O O Ω \Omega Ω
f = O ( g ) f=O(g) f = O ( g ) O ( g ) = f O(g)=f O ( g ) = f Why it feels right: the "=" looks symmetric. Fix: the "=" is a one-way "is a member of." Θ \Theta Θ only symmetric one (f = Θ ( g ) ⟺ g = Θ ( f ) f=\Theta(g)\iff g=\Theta(f) f = Θ ( g ) ⟺ g = Θ ( f )
Recall Feynman: explain to a 12-year-oldImagine guessing how tall a kid will be. Big-O O O Ω \Omega Ω Θ \Theta Θ pretty exactly . We ignore baby photos (small n n n
Mnemonic Remember the shapesO verhead = O = ceiling (≤). Ω looks like an upside-down cup holding things up = floor (≥). Θ has a bar through the middle = pinned th rough the middle = th eta = tight .
Definition of f = Ω ( g ) f=\Omega(g) f = Ω ( g ) ∃ c > 0 , n 0 > 0 : 0 ≤ c g ( n ) ≤ f ( n ) \exists c>0,n_0>0:\ 0\le c\,g(n)\le f(n) ∃ c > 0 , n 0 > 0 : 0 ≤ c g ( n ) ≤ f ( n ) for all
n ≥ n 0 n\ge n_0 n ≥ n 0 (eventual floor).
Definition of f = Θ ( g ) f=\Theta(g) f = Θ ( g ) ∃ c 1 , c 2 , n 0 > 0 : 0 ≤ c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n ) \exists c_1,c_2,n_0>0:\ 0\le c_1g(n)\le f(n)\le c_2g(n) ∃ c 1 , c 2 , n 0 > 0 : 0 ≤ c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n ) for all
n ≥ n 0 n\ge n_0 n ≥ n 0 .
Θ \Theta Θ O O O Ω \Omega Ω f = Θ ( g ) ⟺ f = O ( g ) and f = Ω ( g ) f=\Theta(g) \iff f=O(g)\ \text{and}\ f=\Omega(g) f = Θ ( g ) ⟺ f = O ( g ) and f = Ω ( g ) .
Limit test: if lim f / g = 0 \lim f/g = 0 lim f / g = 0 f = O ( g ) f=O(g) f = O ( g ) but not
Ω ( g ) \Omega(g) Ω ( g ) → strictly smaller order (
o ( g ) o(g) o ( g ) ).
Limit test: if lim f / g = ∞ \lim f/g = \infty lim f / g = ∞ f = Ω ( g ) f=\Omega(g) f = Ω ( g ) but not
O ( g ) O(g) O ( g ) → strictly larger order (
ω ( g ) \omega(g) ω ( g ) ).
Limit test: if 0 < lim f / g < ∞ 0<\lim f/g<\infty 0 < lim f / g < ∞ f = Θ ( g ) f=\Theta(g) f = Θ ( g ) — same growth shape.
Is n 2 = O ( n ) n^2=O(n) n 2 = O ( n ) No;
n ≤ c n\le c n ≤ c can't hold for all large
n n n . But
n 2 = Ω ( n ) n^2=\Omega(n) n 2 = Ω ( n ) .
Why does Ω \Omega Ω Bound symbols measure a function's growth; best/worst/average is a separate axis (which input).
Lower bound for comparison sorting, and why? Ω ( n log n ) \Omega(n\log n) Ω ( n log n ) , from decision-tree height
log 2 ( n ! ) = Θ ( n log n ) \log_2(n!)=\Theta(n\log n) log 2 ( n !) = Θ ( n log n ) .
Which Big-notation relation is symmetric? Θ \Theta Θ :
f = Θ ( g ) ⟺ g = Θ ( f ) f=\Theta(g)\iff g=\Theta(f) f = Θ ( g ) ⟺ g = Θ ( f ) .
Insertion sort: single Θ \Theta Θ No — best
Θ ( n ) \Theta(n) Θ ( n ) , worst
Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) , so overall only
O ( n 2 ) O(n^2) O ( n 2 ) ,
Ω ( n ) \Omega(n) Ω ( n ) .
Roles of c c c n 0 n_0 n 0 c c c ignores constant factors;
n 0 n_0 n 0 ignores small-
n n n behavior.
kills constants and small-n noise
f n cost vs g n reference
constant c and threshold n0
Intuition Hinglish mein samjhoDekho, complexity me teen bhai hote hain: Big-O, Big-Omega aur Big-Theta. Big-O bolta hai "isse zyada slow nahi hoga" — yani upar ki ceiling. Big-Omega (Ω \Omega Ω n 2 n^2 n 2 Θ \Theta Θ tight bound kehte hain.
Formula ka asli jadoo do cheezon me hai: constant c c c n 0 n_0 n 0 c c c n 0 n_0 n 0 n n n n n n f / g f/g f / g 0 0 0 f f f Θ \Theta Θ
Sabse bada confusion: log sochte hain "Ω \Omega Ω O , Ω , Θ O,\Omega,\Theta O , Ω , Θ Ω ( n log n ) \Omega(n\log n) Ω ( n log n )
Yeh matter kyun karta hai? Kyunki Ω \Omega Ω problem ki limit jaante hain. Jaise comparison sorting kabhi n log n n\log n n log n Ω ( n log n ) \Omega(n\log n) Ω ( n log n ) O ( n log n ) O(n\log n) O ( n log n ) optimal hai. Isi tarah Ω \Omega Ω
