Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Time & Space Complexity (Big-O)

Big-O describes how the running time (or memory) of an algorithm grows as the input size n grows. We ignore constants and smaller terms, because for big inputs only the dominant term matters.

Why it matters

A judge runs about 10⁸ simple operations per second. If n = 10⁵:

Algorithm Operations Time
O(n log n) ~1.7 × 10⁶ instant
O(n²) 10¹⁰ ~100 seconds → TLE

Common growth rates (fastest → slowest)

Big-O Name Example
O(1) constant array access a[i], hash map lookup
O(log n) logarithmic binary search, balanced BST operations
O(√n) square root checking if n is prime
O(n) linear one loop over the array
O(n log n) linearithmic merge sort, heap sort, sorting in general
O(n²) quadratic two nested loops, bubble sort
O(n³) cubic three nested loops, Floyd–Warshall
O(2ⁿ) exponential all subsets, naive Fibonacci
O(n!) factorial all permutations

Big-O, Big-Ω, Big-Θ

Best, average, worst case are separate questions: quicksort is Θ(n log n) on average but O(n²) in the worst case.

Analysing loops

for (int i = 0; i < n; i++) sum += a[i];                    // O(n)

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) cnt++;                      // O(n²)

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) cnt++;                  // n(n-1)/2 → still O(n²)

for (int i = 1; i < n; i *= 2) cnt++;                       // O(log n): i = 1, 2, 4, 8 …

for (int i = n; i > 0; i /= 2)
    for (int j = 0; j < i; j++) cnt++;                      // n + n/2 + n/4 + … = 2n → O(n)!

for (int i = 1; i * i <= n; i++) cnt++;                     // O(√n)

Rules: consecutive blocks add (keep the biggest), nested blocks multiply, and loops that halve/double give a log.

The trap in the fifth example: the inner loop shrinks, so the total is a geometric series, not n log n.

Analysing recursion

Count calls × work per call, or write a recurrence.

Code shape Recurrence Complexity
f(n) = f(n-1) + O(1) (factorial) T(n) = T(n−1) + 1 O(n)
binary search T(n) = T(n/2) + 1 O(log n)
merge sort T(n) = 2T(n/2) + n O(n log n)
naive Fibonacci f(n-1) + f(n-2) T(n) = T(n−1) + T(n−2) + 1 O(2ⁿ) (about 1.618ⁿ)
tree traversal T(n) = 2T(n/2) + 1 O(n)
def fib(n):            # O(2^n): the same values are recomputed again and again
    return n if n < 2 else fib(n - 1) + fib(n - 2)

from functools import cache
@cache
def fib_fast(n):       # O(n) with memoization — each value computed once
    return n if n < 2 else fib_fast(n - 1) + fib_fast(n - 2)

Master theorem

For T(n) = a·T(n/b) + O(nᵈ):

Merge sort: a = 2, b = 2, d = 1 → log₂2 = 1 = d → O(n log n). Binary search: a = 1, b = 2, d = 0 → log₂1 = 0 = d → O(log n).

Amortised complexity

vector.push_back / ArrayList.add is usually O(1) but sometimes O(n) when the array doubles. Over n pushes the total copying is n + n/2 + n/4 + … < 2n, so each push is O(1) amortised.

Space complexity

Count the extra memory you allocate (the input usually isn't counted):

Code Extra space
a few variables O(1)
a new array / hash map of n items O(n)
a 2-D DP table n × m O(n·m)
recursion of depth d O(d) — the call stack counts

Recursive DFS on a skewed tree uses O(n) stack; on a balanced tree O(log n).

Reading the constraints

n up to Aim for
10–12 O(n!)
20–25 O(2ⁿ)
500 O(n³)
5,000 O(n²)
10⁵ – 10⁶ O(n log n) or O(n)
10⁹ and more O(log n) or O(1)

Practice: what's the complexity?

  1. Two separate loops of n → O(n).
  2. A loop of n with a binary search inside → O(n log n).
  3. Sort, then one loop → O(n log n).
  4. for i in range(n): for j in range(i, i+5) → O(n) (the inner loop is constant).
  5. Checking every pair with a hash set inside → O(n²) time, O(n) space.

Interview one-liners

More DSA notes