Time Complexity

Time complexity measures how the number of operations an algorithm performs grows with input size. This lesson covers the most common complexities you will encounter, with code examples for each.

O(1) — Constant Time

An algorithm is O(1) if it always performs the same number of operations regardless of input size.

def get_first(items):
    return items[0]   # one operation, always

def is_even(n):
    return n % 2 == 0  # one operation, always

Dictionary (hash map) lookups are O(1) on average — regardless of whether the dictionary has 10 or 10 million keys.

phone_book = {"Alice": "555-0101", "Bob": "555-0102"}
print(phone_book["Alice"])   # O(1) — direct lookup by hash

O(1) is the best possible complexity. Not everything can be O(1), but recognising when something is (or is not) O(1) is essential.

O(log n) — Logarithmic Time

An algorithm is O(log n) if it halves (or similarly reduces) the problem size at each step. Logarithm base 2 is implied in CS unless stated otherwise.

Binary search is the canonical example. To find a value in a sorted list of 1,024 items:

• Step 1: compare to middle → 512 items remain
• Step 2: compare to middle → 256 items remain
• ...
• Step 10: 1 item remains

10 steps for 1,024 items. 20 steps for 1,048,576 items. That is log₂(n) steps.

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

O(log n) algorithms are extremely efficient. Even for n = 1 billion, log₂(1 billion) ≈ 30 steps.

O(n) — Linear Time

An algorithm is O(n) if it performs a fixed number of operations per input element — proportional to input size.

def find_max(nums):
    max_val = nums[0]
    for n in nums:       # visits each element once
        if n > max_val:
            max_val = n
    return max_val

def sum_list(nums):
    total = 0
    for n in nums:       # one addition per element
        total += n
    return total

Two sequential loops (not nested) are still O(n):

def two_passes(nums):
    total = 0
    for n in nums:    # O(n)
        total += n
    for n in nums:    # O(n)
        print(n)
    # Total: O(2n) → O(n)

The constant 2 is dropped. Two sequential O(n) loops is still O(n).

O(n log n) — Linearithmic Time

This complexity appears in efficient sorting algorithms. It is worse than O(n) but dramatically better than O(n²).

Merge sort achieves O(n log n) by recursively splitting the list in half (log n levels) and merging each level (n work per level):

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # recurse on half
    right = merge_sort(arr[mid:])   # recurse on other half
    return merge(left, right)       # merge takes O(n)

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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Python's built-in sorted() and .sort() use Timsort, which is also O(n log n) in the worst case.

O(n²) — Quadratic Time

An algorithm is O(n²) when it has a loop nested inside another loop, each running n times.

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

def find_duplicates_naive(nums):
    duplicates = []
    for i in range(len(nums)):          # O(n)
        for j in range(i + 1, len(nums)):  # O(n)
            if nums[i] == nums[j]:
                duplicates.append(nums[i])
    return duplicates

O(n²) becomes painful quickly. For n = 10,000: 100,000,000 operations. For n = 100,000: 10,000,000,000 operations. Avoid nested loops over the same input whenever possible.

O(2ⁿ) — Exponential Time

Each additional input element doubles the number of operations. This is typical of naive recursive solutions that branch into two subproblems at each step.

def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)  # two recursive calls

For n = 50, this makes ~2^50 ≈ 1 quadrillion calls. Even on fast hardware, this is unusable. Memoisation or dynamic programming drops this to O(n).

Comparing the Complexities

For n = 1,000:

Key Takeaways

• O(1): fixed work regardless of input — array indexing, hash lookups
• O(log n): halving the problem each step — binary search, balanced BST operations
• O(n): one pass over all elements — linear search, sum, max
• O(n log n): divide and merge — efficient sorting (merge sort, Timsort)
• O(n²): nested loops over the same data — bubble sort, naive duplicate detection
• O(2ⁿ): branching recursion — naive Fibonacci, subset enumeration