Understanding Time Complexity: Big O Notation Explained

Time complexity analysis helps you understand how algorithms scale. Big O notation is the standard way to express this.

What is Big O?

Big O gives an upper bound on how an algorithm's running time grows as the input size, written n, grows. It drops constant factors and smaller terms, because once n is large the fastest-growing term decides everything. An algorithm that takes 3n steps and one that takes n steps both double their work when n doubles, so both are O(n).

Common Complexities

O(1), constant time

Operations that take the same time regardless of input size.

def get_first(arr):
    return arr[0]  # Always takes same time

O(log n), logarithmic growth

Operations that halve the problem size each step.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2  # Problem size halves each iteration
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

A sorted list of a million items needs at most 20 passes. The binary search guide covers the boundary variants.

O(n), linear time

Operations that process each element once.

def find_max(arr):
    max_val = arr[0]
    for num in arr:  # Process each element
        if num > max_val:
            max_val = num
    return max_val

O(n log n), linearithmic

Common in efficient sorting algorithms.

# Merge sort, Quick sort
sorted_arr = sorted(arr)  # O(n log n)

Merge sort shows where the log comes from. It splits the list in half until every piece holds one item, which takes about log n levels. Merging the pieces back touches every item once per level, so the total is n work on each of log n levels. Quicksort is O(n log n) on average, but unlucky pivots make it O(n²).

O(n²), quadratic time

Nested loops over the same data.

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr) - 1):  # Nested loop
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Working out the complexity of your own code

Code run one block after another adds, and a loop inside a loop multiplies. Sort a list and then scan it once, and you get n log n plus n, which is O(n log n) because the smaller term drops.

Three mistakes come up often. The first is calling loops over two different inputs O(n²). With a items in one list and b in the other, nesting the loops gives O(ab) and running them back to back gives O(a + b).

The second is missing a linear cost hidden inside one line. In Python, x in some_list scans the list, pop(0) shifts every remaining item, and arr[1:] copies the rest of the list. Put any of these inside a loop and an O(n) plan becomes O(n²). Both functions below drop repeated values from a list.

def unique_slow(items):
    seen = []
    for x in items:
        if x not in seen:  # scans the list: O(n) per check
            seen.append(x)
    return seen

def unique_fast(items):
    seen = set()
    result = []
    for x in items:
        if x not in seen:  # hash lookup: O(1) on average
            seen.add(x)
            result.append(x)
    return result

On 20,000 distinct numbers, the first version took over two seconds on a laptop and the second under two milliseconds.

The third mistake is the reverse, assuming a while loop inside a for loop must be O(n²). If the inner loop moves a pointer that only goes forward, that pointer takes at most n steps over the whole run, so the total is O(n). The sliding window technique depends on exactly this.

Using the input size to pick a target

The largest n in the constraints tells you which classes can finish in time. Exponential work is fine up to about n = 20, since 2²⁰ is roughly a million. O(n²) is fine up to a few thousand, because 5,000² is 25 million steps. At n = 100,000 you need O(n log n) or better, since n² would be ten billion steps and n log n is about 1.7 million.

Big O, Omega, and Theta

Big O is an upper bound, so it is technically true that find_max is O(n²), though not useful. Big Omega (Ω) is a lower bound, and Big Theta (Θ) means the two bounds match. find_max is Θ(n), because it reads every item on every input.

Best, worst, and average case are a separate question. Searching an unsorted list takes one step when the value comes first and n steps when it is missing, so the worst case is Θ(n) and the best case is Θ(1). When people say "O(n)" in an interview, they almost always mean a tight bound on the worst case.

Space Complexity

Space complexity follows similar rules but measures memory usage instead of time. bubble_sort sorts in place, so it uses O(1) extra space, while unique_fast uses O(n) for its set. Recursion counts too, because each call that has not returned yet holds memory. Recursing down a linked list of n nodes keeps n calls open at once, so it uses O(n) space.

Quick Reference

• O(1) for typical hash map lookup
• O(log n) for binary search on sorted input
• O(n) for a single linear scan
• O(n log n) for efficient comparison sorts
• O(n²) for many naive nested-loop solutions
• O(2ⁿ) for naive recursive Fibonacci without memoization

LeetCode interview tips shows where this analysis fits in an interview.