T TestsWorld
← All topic guides

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

  1. Count what changes the loop variable. i++ means linear, i *= 2 means logarithmic, i * i <= n means O(√n).
  2. Dependent inner loops. If the inner bound depends on i, write the sum; if it simplifies to something like n²/2, drop the constant.
  3. 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

  1. Multiplying sequential loops. Two loops one after the other are O(n + n) = O(n), not O(n²).
  2. Assuming every nested loop is O(n²). Check the bounds; Example 3 is linear.
  3. Forgetting hidden costs. String concatenation in a loop, list.insert(0, x) or x in list are each O(n) inside the loop.
  4. 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.
  5. 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

Ready to practise Complexity (Big-O)?
Take a free mock test

Related guides