Intuition The one-sentence WHYComplexity classes are a vocabulary for growth : they tell you how fast the work explodes as the input n grows — so you can predict whether your code finishes in milliseconds or in the lifetime of the universe, before you ever run it.
We rank algorithms by how their step count T(n) scales as n → ∞. From fastest (best) to slowest (worst):
O ( 1 ) < O ( log n ) < O ( n ) < O ( n log n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) O ( 1 ) < O ( log n ) < O ( n ) < O ( n log n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n !) The < here means "grows strictly slower for large n". We drop constants and lower-order terms because for huge n only the dominant term matters (that's the whole point of asymptotics — see 3.1.01-Big-O-Notation ).
Definition O(1) — ConstantWork does not depend on n. A fixed number of operations no matter how big the input.
Why constant? There is no loop over the data — you touch a bounded number of elements.
Example: arr[i], stack.push(), hash table lookup (average case).
Definition O(log n) — LogarithmicEach step throws away a fixed fraction of the remaining input (usually half).
Derivation: Start with n items. After k halvings you have n / 2 k n/2^k n / 2 k n 2 k = 1 ⇒ 2 k = n ⇒ k = log 2 n . \frac{n}{2^k} = 1 \;\Rightarrow\; 2^k = n \;\Rightarrow\; k = \log_2 n. 2 k n = 1 ⇒ 2 k = n ⇒ k = log 2 n . k, the number of steps, is = = log 2 n = = ==\log_2 n== == log 2 n == Example: binary search.
You do constant work once per element : T ( n ) = c ⋅ n T(n) = c\cdot n T ( n ) = c ⋅ n Example: find max in an unsorted array.
Definition O(n log n) — LinearithmicYou do a logarithmic number of passes , each pass being linear — OR you split into halves recursively and merge in linear time.
Derivation (merge sort): Recurrence T ( n ) = 2 T ( n / 2 ) + c n T(n) = 2T(n/2) + cn T ( n ) = 2 T ( n /2 ) + c n log 2 n \log_2 n log 2 n c n cn c n = c n ⋅ log 2 n = O ( n log n ) = cn \cdot \log_2 n = O(n\log n) = c n ⋅ log 2 n = O ( n log n ) Example: merge sort, heap sort, fast comparison sorting.
Definition O(n²) — QuadraticFor each element you do work proportional to all elements: a nested loop.
Derivation: ∑ i = 1 n n = n ⋅ n = n 2 \sum_{i=1}^{n} n = n\cdot n = n^2 ∑ i = 1 n n = n ⋅ n = n 2 i i i 1 1 1 n n n i i i n n n ∑ i = 1 n i = n ( n + 1 ) 2 = O ( n 2 ) \sum_{i=1}^{n} i = \frac{n(n+1)}{2} = O(n^2) ∑ i = 1 n i = 2 n ( n + 1 ) = O ( n 2 ) Example: bubble sort, comparing all pairs.
Three nested loops, each running n times: n ⋅ n ⋅ n = n 3 n \cdot n \cdot n = n^3 n ⋅ n ⋅ n = n 3 Example: naive matrix multiplication of two n×n matrices.
Definition O(2ⁿ) — ExponentialEach added element doubles the work, because you make a binary choice (take / skip) at every step.
Derivation: number of subsets of n items = 2 n 2^n 2 n T ( n ) = 2 T ( n − 1 ) + c T(n) = 2T(n-1) + c T ( n ) = 2 T ( n − 1 ) + c 2 n 2^n 2 n Example: naive recursive Fibonacci, brute-force subset enumeration.
Definition O(n!) — FactorialYou enumerate every ordering (permutation) of n items: n ! = n ⋅ ( n − 1 ) ⋯ 1 n! = n\cdot(n-1)\cdots 1 n ! = n ⋅ ( n − 1 ) ⋯ 1 Example: brute-force Travelling Salesman, generating all permutations.
Worked example Forecast first, then checkForecast: "For n = 10, which is bigger: n² or 2ⁿ?"
Many guess 2ⁿ is always huge — but at n=10: n² = 100, 2ⁿ = 1024. Here 2ⁿ wins. Why? Exponential has already crossed quadratic by n≈4.
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⁶⁴
Why this matters: at ~10 9 10^9 1 0 9 O(n!) with n=20 already takes ~77 years. That's why exponential/factorial algorithms are "intractable" for large inputs.
Worked example Identify the complexity — workedfor i in range(n): # runs n times
for j in range(i, n): # runs n-i times
do_constant_work()
Why count this way? Total work = ∑ i = 0 n − 1 ( n − i ) = n + ( n − 1 ) + ⋯ + 1 = n ( n + 1 ) 2 = \sum_{i=0}^{n-1}(n-i) = n + (n-1) + \dots + 1 = \frac{n(n+1)}{2} = ∑ i = 0 n − 1 ( n − i ) = n + ( n − 1 ) + ⋯ + 1 = 2 n ( n + 1 ) Why drop the ½ and the +n? Asymptotically the n 2 n^2 n 2 O ( n 2 ) O(n^2) O ( n 2 )
Worked example Logarithmic spottingwhile n > 1:
n = n // 2 # halve each iteration
Why O(log n)? The variable is divided by 2 each step → number of iterations is log 2 ( start ) \log_2(\text{start}) log 2 ( start ) signature of log is dividing the problem by a constant factor , not subtracting.
Common mistake "Two separate loops = O(n²)"Why it feels right: "two loops, so multiply."
The truth: Loops in sequence add : O ( n ) + O ( n ) = O ( 2 n ) = O ( n ) O(n)+O(n)=O(2n)=O(n) O ( n ) + O ( n ) = O ( 2 n ) = O ( n ) nested loops multiply . Fix: ask "is this loop inside the other?"
Common mistake "O(log n) base matters"Why it feels right: log 2 \log_2 log 2 log 10 \log_{10} log 10 The truth: log b n = log 2 n log 2 b \log_b n = \frac{\log_2 n}{\log_2 b} log b n = l o g 2 b l o g 2 n constant , which Big-O drops. So O ( log n ) O(\log n) O ( log n ) log n.
Common mistake "O(2ⁿ) and O(n!) are basically the same — both 'super slow'."Why it feels right: both are 'exponential-ish' and useless for big n.
The truth: n ! n! n ! far faster: at n=20, 2ⁿ≈10⁶ but n!≈2.4×10¹⁸ — a trillion times bigger. Fix: factorial is its own, worse class.
Common mistake "Lower complexity always wins."Why it feels right: asymptotics say so.
The truth: Big-O hides constants. For small n, an O(n²) with tiny constant can beat an O(n log n) with huge constant (e.g. insertion sort beats merge sort for n<~20). Fix: asymptotics describe large n; profile for small inputs.
Recall Feynman: explain to a 12-year-oldImagine you have a giant pile of homework sheets n.
O(1): you only check the top sheet — same effort no matter how tall the pile.O(log n): it's a sorted pile and you play "higher/lower", tearing the pile in half each guess — even a million sheets takes ~20 guesses.O(n): you read every sheet once.O(n²): for every sheet, you compare it to every other sheet (gossip: everyone talks to everyone).O(2ⁿ): for each sheet you decide keep-or-toss, and you try every combination — the choices double each new sheet.O(n!): you try every possible order to stack them — hopeless past a handful.
The faster the pile of work explodes when sheets are added, the worse the algorithm.
Mnemonic Remember the ladder"Constant Logs Never Nag Squares; Cubes Explode Factorially."
1 , log n , n , n log n , n 2 , n 3 , 2 n , n ! 1,\ \log n,\ n,\ n\log n,\ n^2,\ n^3,\ 2^n,\ n! 1 , log n , n , n log n , n 2 , n 3 , 2 n , n !
Which complexity has step count independent of n? O(1) — constant.
Why is binary search O(log n)? Each step halves the search space;
n / 2 k = 1 ⇒ k = log 2 n n/2^k=1 \Rightarrow k=\log_2 n n / 2 k = 1 ⇒ k = log 2 n .
Two sequential O(n) loops give what complexity? O(n) — sequential loops add, not multiply.
Why is the log base irrelevant in O(log n)? Changing base multiplies by a constant (
log b n = log 2 n / log 2 b \log_b n=\log_2 n/\log_2 b log b n = log 2 n / log 2 b ), and Big-O drops constants.
Derive the complexity of merge sort. T ( n ) = 2 T ( n / 2 ) + c n T(n)=2T(n/2)+cn T ( n ) = 2 T ( n /2 ) + c n ; recursion tree has
log 2 n \log_2 n log 2 n levels of
c n cn c n work each →
O ( n log n ) O(n\log n) O ( n log n ) .
What is ∑ i = 1 n i \sum_{i=1}^{n} i ∑ i = 1 n i n ( n + 1 ) 2 = O ( n 2 ) \frac{n(n+1)}{2}=O(n^2) 2 n ( n + 1 ) = O ( n 2 ) .
Where does O(2ⁿ) come from in subset problems? Each element is take/skip →
2 n 2^n 2 n subsets; or recurrence
T ( n ) = 2 T ( n − 1 ) + c T(n)=2T(n-1)+c T ( n ) = 2 T ( n − 1 ) + c .
Which grows faster, 2ⁿ or n!, and why? n! — it's a product of n factors most of which exceed 2; overtakes 2ⁿ from n=4.
At n=10, compare n² and 2ⁿ. n²=100, 2ⁿ=1024; exponential already larger past n≈4.
Naive n×n matrix multiplication is what complexity? O(n³) — three nested loops.
Order these: O(n!), O(1), O(n log n), O(2ⁿ), O(n²). O(1) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).
Signature of O(log n) in code? A variable divided/multiplied by a constant factor each iteration (not subtracted).
Intuition Hinglish mein samjhoDekho, complexity classes basically ek "growth ka vocabulary" hain. Sawaal yeh hai: jaise-jaise input n bada hota hai, tumhare code ka kaam kitni tezi se badhta hai? Agar kaam constant rehta hai (O(1)) to mast — input chahe ek ho ya ek crore, same time. Agar har step me problem aadhi ho jaati hai (jaise binary search), to woh O(log n) — bahut slow grow karta hai, kyunki n / 2 k = 1 n/2^k = 1 n / 2 k = 1 k = log 2 n k = \log_2 n k = log 2 n
Phir O(n) matlab har element ko ek baar chhuo, O(n log n) matlab merge sort jaisa (log levels, har level pe linear kaam). Nested loops aate hi cheezein multiply hoti hain: O(n²), O(n³). Aur jab har element pe "take ya skip" jaisa choice hota hai to O(2ⁿ) — exponential, aur jab saare orderings try karne padein to O(n!) — factorial, sabse worst.
Sabse important practical baat: O(2ⁿ) aur O(n!) bade n ke liye "intractable" hote hain. n=20 pe n! ka matlab 77 saal lag sakte hain ek normal computer pe! Isiliye hum dynamic programming jaise tricks se exponential ko polynomial me convert karte hain. Yaad rakhna — sequential loops add hote hain (O(n)+O(n)=O(n)), sirf nested loops multiply karte hain. Aur log ka base matter nahi karta kyunki woh sirf ek constant se multiply hota hai jo Big-O drop kar deta hai.
