Complexity Analysis

Big O Notation

How fast does your code grow when input size grows? Master this and you'll analyse any algorithm.

Key concept Growth Rate
Not actual seconds — relative growth
Big O Growth Rate Visualizer

See how different complexities grow as n increases. Drag the slider to change n.

n=1,000,000 — Steps Comparison

The 3 Golden Rules

Drop Constants
O(2n) → O(n)  |  O(100) → O(1)
Constants don't change the growth rate.
Drop Smaller Terms
O(n² + n) → O(n²)
At large n, n² completely dominates n.
Nested = Multiply, Sequential = Add then Drop
Two separate loops → O(n). Nested loops → O(n²).
# Sequential → O(n) + O(n) = O(2n) → O(n)
for i in range(n): ...
for i in range(n): ...

# Nested → O(n) × O(n) = O(n²)
for i in range(n):
    for j in range(n): ...

# Log n: each step HALVES the problem
while n > 1:
    n = n // 2   # O(log n)

What is Big O?

Core Intuition
"When input size n doubles, how many more steps does my code take?" — That's growth rate. Big O = worst case growth.
ComplexityNamen = 1M stepsVerdict
O(1)Constant1Perfect
O(log n)Logarithmic~20Excellent
O(n)Linear1,000,000Good
O(n log n)Linearithmic~20,000,000Acceptable
O(n²)Quadratic1,000,000,000,000Slow ❌
O(2ⁿ)Exponential∞Never use ❌

Space Complexity

Key Question
Did I create new memory that grows with input? Array of size n → O(n). Recursion depth n → O(n) stack. A few variables → O(1).
What you createSpace
A few integer variablesO(1)
Array/list of size nO(n)
2D matrix n×nO(n²)
Recursion depth nO(n) call stack
HashMap with n entriesO(n)

Common Mistakes

Mistake 1
Thinking O(1) means "fast". It means constant — could be a million operations, but that million doesn't grow with n.
Mistake 2
Forgetting that built-in operations have complexity too: x in list is O(n), x in set is O(1), sorted() is O(n log n).
Mistake 3
Counting only loops, ignoring recursive calls. A recursive function that calls itself twice per call is O(2ⁿ).

Code Pattern → Complexity

PatternTimeWhy
Single loop over nO(n)Runs n times
Two nested loopsO(n²)n × n
Halve input each stepO(log n)log₂(n) steps
arr.sort()O(n log n)TimSort
dict / set lookupO(1)Hash function
Recursion branches 2×O(2ⁿ)Tree of calls
x in listO(n)Linear scan
list.pop(0)O(n)Shifts all elements
deque.popleft()O(1)Double-ended

Python Specific — Know These!

# O(1) operations
arr[i]             # index access
arr.append(x)      # amortized O(1)
arr.pop()          # remove last
d[key]             # dict access
x in my_set       # set lookup
len(anything)      # stored attribute

# O(n) operations — be careful!
x in my_list       # linear scan ❌
arr.insert(0, x)   # shifts all right ❌
arr.pop(0)         # shifts all left ❌
arr.copy()         # copies n elements
" ".join(arr)      # O(total chars)

# O(n log n)
arr.sort()         # in-place TimSort
sorted(arr)        # returns new sorted list

Determine the Complexity

LeetCode Problems to Practice

  • EasyContains DuplicateO(n) with Set
  • EasyTwo SumO(n) with HashMap
  • MediumTop K Frequent ElementsO(n log k) Heap
  • MediumMeeting Rooms IIO(n log n) sort