3.1.2
Intuition Ek sentence mein WHYComplexity classes ek growth ki vocabulary hain: ye batati hain ki kaam kitni tezi se badhta hai jab input n badhta hai — taaki tum predict kar sako ki tumhara code milliseconds mein khatam hoga ya universe ki lifetime mein, code run karne se pehle hi.
Hum algorithms ko rank karte hain ki unka step count T(n) kaise scale karta hai jab n → ∞. Fastest (best) se slowest (worst) tak:
O ( 1 ) < O ( log n ) < O ( n ) < O ( n log n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n !) Yahan < ka matlab hai "bade n ke liye strictly slower grow karta hai". Hum constants aur lower-order terms drop kar dete hain kyunki bahut bade n ke liye sirf dominant term matter karta hai (yahi asymptotics ka poora point hai — dekho 3.1.01-Big-O-Notation ).
Definition O(1) — ConstantKaam n par depend nahi kartaConstant kyun? Data pe koi loop nahi hota — tum ek bounded number of elements ko touch karte ho.
Example: arr[i], stack.push(), hash table lookup (average case).
Definition O(log n) — LogarithmicHar step mein remaining input ka ek fixed fraction throw away ho jaata hai (usually aadha).
Derivation: n items se shuru karo. k halvings ke baad n / 2 k 2 k n = 1 ⇒ 2 k = n ⇒ k = log 2 n . k, steps ki count, == log 2 n == Example: binary search.
Tum har element ke liye ek baar constant kaam karte ho: T ( n ) = c ⋅ n Example: unsorted array mein max dhundho.
Definition O(n log n) — LinearithmicTum logarithmic number of passes karte ho, har pass linear hoti hai — YA recursively halves mein split karte ho aur linear time mein merge karte ho.
Derivation (merge sort): Recurrence T ( n ) = 2 T ( n /2 ) + c n log 2 n c n = c n ⋅ log 2 n = O ( n log n ) Example: merge sort, heap sort, fast comparison sorting.
Definition O(n²) — QuadraticHar element ke liye tum sab elements ke proportional kaam karte ho: ek nested loop.
Derivation: ∑ i = 1 n n = n ⋅ n = n 2 i 1 n i n ∑ i = 1 n i = 2 n ( n + 1 ) = O ( n 2 ) Example: bubble sort, saare pairs ko compare karna.
Teen nested loops, har ek n baar chalti hai: n ⋅ n ⋅ n = n 3 Example: do n×n matrices ka naive matrix multiplication.
Definition O(2ⁿ) — ExponentialHar added element kaam ko double kar deta hai , kyunki tum har step par ek binary choice karte ho (lo / skip karo).
Derivation: n items ke subsets ki sankhya = 2 n T ( n ) = 2 T ( n − 1 ) + c 2 n Example: naive recursive Fibonacci, brute-force subset enumeration.
Definition O(n!) — FactorialTum n items ki har ordering (permutation) enumerate karte ho: n ! = n ⋅ ( n − 1 ) ⋯ 1 Example: brute-force Travelling Salesman, saari permutations generate karna.
Worked example Pehle forecast karo, phir check karoForecast: "n = 10 ke liye, kaunsa bada hai: n² ya 2ⁿ?"
Bahut log guess karte hain ki 2ⁿ hamesha huge hota hai — lekin n=10 par: n² = 100, 2ⁿ = 1024. Yahan 2ⁿ jeet jaata hai. Kyun? Exponential quadratic ko n≈4 par hi cross kar leta hai.
n
log₂n
n
n log n
n²
2ⁿ
n!
10
3.3
10
33
100
1 024
3.6×10⁶
20
4.3
20
86
400
~10⁶
2.4×10¹⁸
50
5.6
50
282
2 500
~10¹⁵
3×10⁶⁴
Yeh kyun matter karta hai: ~1 0 9 O(n!) ke saath n=20 mein already ~77 saal lagte hain. Isliye exponential/factorial algorithms bade inputs ke liye "intractable" kehlaate hain.
Worked example Complexity identify karo — worked examplefor i in range(n): # runs n times
for j in range(i, n): # runs n-i times
do_constant_work()
Is tarah count kyun karte hain? Total kaam = ∑ i = 0 n − 1 ( n − i ) = n + ( n − 1 ) + ⋯ + 1 = 2 n ( n + 1 ) ½ aur +n kyun drop karte hain? Asymptotically n 2 O ( n 2 )
Worked example Logarithmic spottingwhile n > 1:
n = n // 2 # halve each iteration
O(log n) kyun? Variable har step mein 2 se divide ho raha hai → iterations ki sankhya log 2 ( start ) Log ki signature hai problem ko ek constant factor se divide karna , subtract nahi karna.
Common mistake "Do alag loops = O(n²)"Sahi kyun lagta hai: "do loops hain, to multiply karo."
Sachai: Sequence mein loops add hote hain: O ( n ) + O ( n ) = O ( 2 n ) = O ( n ) nested loops multiply hote hain. Fix: pucho "kya yeh loop doosre ke andar hai?"
Common mistake "O(log n) mein base matter karta hai"Sahi kyun lagta hai: log 2 log 10 Sachai: log b n = l o g 2 b l o g 2 n constant se multiply karta hai, jo Big-O drop kar deta hai. To O ( log n ) log n likho.
Common mistake "O(2ⁿ) aur O(n!) basically same hain — dono 'super slow'."Sahi kyun lagta hai: dono 'exponential-ish' hain aur bade n ke liye useless hain.
Sachai: n ! bahut zyada tezi se badhta hai: n=20 par, 2ⁿ≈10⁶ lekin n!≈2.4×10¹⁸ — ek trillion guna bada. Fix: factorial apni alag, worse class hai.
Common mistake "Lower complexity hamesha jeetegi."Sahi kyun lagta hai: asymptotics yahi kehti hain.
Sachai: Big-O constants hide karta hai. Chhote n ke liye, tiny constant wala O(n²) huge constant wale O(n log n) ko beat kar sakta hai (jaise insertion sort merge sort ko n<~20 ke liye beat karta hai). Fix: asymptotics bade n describe karta hai; chhote inputs ke liye profile karo.
Recall Feynman: ek 12 saal ke bacche ko explain karoSocho tumhare paas homework sheets ka ek bada dhair hai n.
O(1): tum sirf sabse upar wali sheet check karte ho — kitna bhi uncha dhair ho, effort same rahta hai.O(log n): yeh ek sorted dhair hai aur tum "upar/neeche" khel rahe ho, dhair ko har guess mein aadha tod rahe ho — ek million sheets bhi ~20 guesses mein ho jaata hai.O(n): tum har sheet ek baar padhte ho.O(n²): har sheet ke liye tum use har doosri sheet se compare karte ho (gossip: sabse sabse baat karta hai).O(2ⁿ): har sheet ke liye tum rakh-lo-ya-phenko decide karte ho, aur tum har combination try karte ho — choices har nayi sheet ke saath double ho jaati hain.O(n!): tum unhe stack karne ka har possible order try karte ho — thodi si sheets ke baad hi hopeless hai.
Jitni tezi se kaam ka dhair sheets add karne par badhta hai, utna bura algorithm hai.
Mnemonic Ladder yaad karo"Constant Logs Never Nag Squares; Cubes Explode Factorially."
1 , log n , n , n log n , n 2 , n 3 , 2 n , n !
Kaun si complexity hai jiska step count n se independent hai? O(1) — constant.
Binary search O(log n) kyun hai? Har step search space ko aadha karta hai; n / 2 k = 1 ⇒ k = log 2 n
Do sequential O(n) loops ki complexity kya hogi? O(n) — sequential loops add hote hain, multiply nahi.
O(log n) mein log base irrelevant kyun hai? Base change sirf ek constant se multiply karta hai (log b n = log 2 n / log 2 b
Merge sort ki complexity derive karo. T ( n ) = 2 T ( n /2 ) + c n c n log 2 n O ( n log n )
∑ i = 1 n i 2 n ( n + 1 ) = O ( n 2 )
Subset problems mein O(2ⁿ) kahan se aata hai? Har element take/skip hai → 2 n T ( n ) = 2 T ( n − 1 ) + c
2ⁿ ya n! mein se kaunsa faster grow karta hai, aur kyun? n! — yeh n factors ka product hai jinmein zyaadatar 2 se bade hain; n=4 se 2ⁿ ko overtake karta hai.
n=10 par n² aur 2ⁿ compare karo. n²=100, 2ⁿ=1024; exponential n≈4 ke baad se pehle se bada hai.
Naive n×n matrix multiplication ki complexity kya hai? O(n³) — teen nested loops.
In sab ko order karo: O(n!), O(1), O(n log n), O(2ⁿ), O(n²). O(1) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).
Code mein O(log n) ki signature kya hai? Har iteration mein ek variable constant factor se divide/multiply hota hai (subtract nahi).
