Time Complexity

What Is Time Complexity?

Time complexity is a measure of how the number of operations an algorithm performs grows as the input size grows. It is not about wall-clock seconds — it abstracts away hardware speed, language overhead, and constants to reveal the underlying shape of the algorithm.

We express time complexity using asymptotic notation. The three most common forms are:

• Big-O (O) — upper bound. The algorithm does at most this many operations.
• Big-Omega (Ω) — lower bound. The algorithm does at least this many operations.
• Big-Theta (Θ) — tight bound. The algorithm does exactly this order of operations in both best and worst case.

In practice, when engineers say "Big-O," they usually mean the worst-case tight bound. That's the convention used throughout this track.

The Common Complexity Classes

O(1) — Constant Time

The algorithm does the same number of operations regardless of input size.

def get_first(arr):
    return arr[0]

Accessing an element by index in an array is O(1). It doesn't matter if the array has 10 or 10 million elements — the operation takes the same time.

Other O(1) examples: hash map lookup (average case), stack push/pop, queue enqueue/dequeue.

O(log n) — Logarithmic Time

The algorithm halves (or reduces by a constant factor) the problem size at each step.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

For an array of n=1,000,000 elements, binary search takes at most log₂(1,000,000) ≈ 20 comparisons. Doubling n only adds one more step. This is the power of logarithmic algorithms.

Other O(log n) examples: balanced BST lookup, heap insertion, finding the number of digits in an integer.

O(n) — Linear Time

The algorithm processes each element of the input once.

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Best case: target is the first element — O(1). Worst case: target is last or absent — O(n). We report O(n).

Other O(n) examples: finding max/min, counting occurrences, summing an array, copying an array.

O(n log n) — Linearithmic Time

The algorithm does O(log n) work for each of the n elements, or divides the problem in half O(log n) times while doing O(n) work at each level.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

Merge sort splits the array log n times (depth of recursion tree), and at each level it does O(n) merge work. Total: O(n log n).

This is the best achievable complexity for comparison-based sorting (proven lower bound).

O(n²) — Quadratic Time

The algorithm uses a nested loop where both iterate over n elements.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

For n=1000 elements, bubble sort performs up to ~500,000 comparisons. For n=10,000, it's ~50,000,000. It grows with the square of the input.

Other O(n²) examples: insertion sort, selection sort, checking all pairs in an array.

O(2ⁿ) — Exponential Time

The algorithm explores all subsets or all possible combinations. The work doubles with each additional element.

def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

fibonacci_naive(50) would require approximately 2⁵⁰ ≈ 10¹⁵ calls. Exponential algorithms are only practical for very small inputs (typically n < 30).

Other O(2ⁿ) examples: generating all subsets, brute-force traveling salesman, naive backtracking.

O(n!) — Factorial Time

The algorithm generates all permutations of the input.

def permutations(arr):
    if len(arr) <= 1:
        return [arr]
    result = []
    for i, val in enumerate(arr):
        rest = arr[:i] + arr[i+1:]
        for perm in permutations(rest):
            result.append([val] + perm)
    return result

For n=10, there are 3,628,800 permutations. For n=20, there are 2.4 × 10¹⁸. Factorial algorithms are almost never practical beyond n=12 or so.

How to Analyze Algorithms

Single Loops

A single loop that runs n times is O(n):

for i in range(n):      # n iterations
    do_constant_work()  # O(1) each
# Total: O(n)

If the loop runs n/2 times or 2n times, it's still O(n) — constants are dropped.

Nested Loops

Two nested loops, each running n times, is O(n²):

for i in range(n):          # n iterations
    for j in range(n):      # n iterations each
        do_constant_work()  # O(1) each
# Total: O(n²)

If the inner loop runs from j=i to n (upper triangle), the total is n*(n+1)/2 ≈ n²/2 iterations — still O(n²).

Sequential Blocks

Add complexities of sequential sections, then keep the dominant term:

for i in range(n):       # O(n)
    do_work()
 
for i in range(n):       # O(n)
    for j in range(n):   # O(n²) total for this block
        do_work()
 
# Total: O(n) + O(n²) = O(n²)

O(n²) dominates, so we drop O(n).

Loops with Non-Linear Increments

Not all loops run n times. Look carefully at the increment:

i = 1
while i < n:    # i = 1, 2, 4, 8, ... — log n iterations
    i *= 2
# Total: O(log n)

i = n
while i > 0:   # i = n, n/2, n/4, ... — log n iterations
    i //= 2
# Total: O(log n)

Analyzing Recursion

For recursive algorithms, count the total number of calls and work per call:

def sum_array(arr, n):
    if n == 0:
        return 0
    return arr[n-1] + sum_array(arr, n-1)

Each call does O(1) work and makes 1 recursive call. Total calls: n. Total: O(n).

For algorithms that branch (multiple recursive calls), use a recurrence relation and solve it — which is exactly what the Master Theorem article covers next.

Dropping Constants and Lower-Order Terms

Big-O notation drops:

• Constants: O(2n) → O(n), O(n/2) → O(n), O(500) → O(1)
• Lower-order terms: O(n² + n) → O(n²), O(n log n + n) → O(n log n)

This is valid because as n grows toward infinity, the dominant term overwhelms everything else. We care about rate of growth, not the exact count.

Best, Average, and Worst Case

For any algorithm, there are three scenarios to consider:

When someone says "Quick Sort is O(n log n)," they mean the average case. The worst case is O(n²), which is why production implementations use randomized pivots or hybrid approaches like Timsort.

Comparing Growth Rates

For large n, the ordering is:

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

To develop intuition, here's how many operations each requires for n = 1,000,000:

A Note on Amortized Complexity

Some data structures have operations that are occasionally expensive but cheap on average. Dynamic arrays (like Python lists or Java ArrayLists) are the canonical example.

Appending to a dynamic array is usually O(1). But when the array is full, it doubles in size — copying all n elements — which is O(n). Amortized over n appends, the total work is O(n), so each append is amortized O(1).

Amortized analysis gives you a more accurate picture of real-world performance than pure worst-case analysis.

Summary

• O(1) — does not grow with input (array index, hash map lookup)
• O(log n) — halves the problem each step (binary search, balanced BST)
• O(n) — touches each element once (linear scan, array sum)
• O(n log n) — divide-and-conquer over linear work (merge sort)
• O(n²) — nested loops over n elements (bubble sort, all pairs)
• O(2ⁿ) — explores all subsets (fibonacci naive, backtracking)
• Drop constants and lower-order terms
• Report worst case unless otherwise stated

Next: Space Complexity — how to measure and reason about memory usage.