Complexity (Big-O): formulas, shortcuts & solved examples
What it is
Time complexity describes how the number of basic operations grows as the input size n grows. Big-O gives an upper bound, ignoring constants and lower-order terms, so 3n² + 5n + 7 is O(n²). Coding rounds ask you to state the complexity of a snippet or pick the fastest approach that fits the limits.
Key rules
Notation
- O(f(n)): grows no faster than f(n) (upper bound).
- Ω(f(n)): grows at least as fast as f(n) (lower bound).
- Θ(f(n)): both, a tight bound.
Common growth order
O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
Loop rules
- Sequential blocks: add and keep the largest term. O(n) + O(n²) = O(n²).
- Nested loops: multiply. Two independent loops to n give O(n²).
- Loop variable multiplied or divided by a constant each step: O(log n).
- Inner loop running i times for i = 0..n−1: total n(n − 1) / 2, still O(n²).
- Halving work each pass (n + n/2 + n/4 + ...): sum < 2n, so O(n).
Master theorem (for T(n) = aT(n/b) + O(nᵈ))
- If d > log_b a: O(nᵈ)
- If d = log_b a: O(nᵈ log n)
- If d < log_b a: O(n^(log_b a))
Merge sort: a = 2, b = 2, d = 1, so O(n log n). Binary search: a = 1, b = 2, d = 0, so O(log n).
Typical operation budget
A rough rule used in competitive programming is around 10⁸ simple operations per second. With n = 10⁵, O(n²) = 10¹⁰ is too slow, while O(n log n) ≈ 1.7 × 10⁶ is comfortable.
Shortcuts
- Count what changes the loop variable.
i++means linear,i *= 2means logarithmic,i * i <= nmeans O(√n). - Dependent inner loops. If the inner bound depends on i, write the sum; if it simplifies to something like n²/2, drop the constant.
- Recursion tree. Branching factor b and depth d give about bᵈ calls; naive Fibonacci has branching 2 and depth n, hence O(2ⁿ).
Solved examples
Example 1: Doubling loop
count, i, n = 0, 1, 16
while i < n:
i *= 2
count += 1
print(count)
Solution. i takes values 1, 2, 4, 8, then 16 stops the loop. The body ran 4 times, which is log₂ 16. Complexity: O(log n).
Example 2: Triangular nested loop
count, n = 0, 8
for i in range(n):
for j in range(i):
count += 1
print(count)
Solution. The inner loop runs 0 + 1 + ... + 7 = 8 × 7 / 2 = 28 times. In general n(n − 1)/2, so the complexity is O(n²), even though it does about half the work of a full square loop.
Example 3: Shrinking outer loop
count, n = 0, 16
i = n
while i > 0:
for j in range(i):
count += 1
i //= 2
print(count)
Solution. The inner loop runs 16 + 8 + 4 + 2 + 1 = 31 times, which is less than 2n. The outer loop runs log n times, but the total work is a geometric series, so the complexity is O(n), not O(n log n). This is a favourite trick question.
Example 4: Choosing an approach
You must check whether any two numbers in an array of n = 10⁵ salaries add up to a target. Compare a double loop with a hash-set approach.
Solution. The double loop checks every pair: n(n − 1)/2 ≈ 5 × 10⁹ comparisons, O(n²), too slow. The hash-set method walks the array once, checking whether target − x is already in the set: O(n) average time with O(n) extra space. Sorting plus two pointers gives O(n log n) time with O(1) extra space. Pick based on whether memory or time is tighter.
Common mistakes
- Multiplying sequential loops. Two loops one after the other are O(n + n) = O(n), not O(n²).
- Assuming every nested loop is O(n²). Check the bounds; Example 3 is linear.
- Forgetting hidden costs. String concatenation in a loop,
list.insert(0, x)orx in listare each O(n) inside the loop. - Confusing average and worst case. Hash lookups are O(1) on average but O(n) in the worst case; quicksort is O(n log n) average and O(n²) worst.
- Ignoring space complexity. Recursion uses stack space proportional to depth, so a recursive linear scan uses O(n) space.
Practice now: https://www.testsworld.com/mocks