Time Complexity and Big O Notation: How to Measure Algorithm Speed

Stop guessing whether your code is fast — learn to measure it properly.

---

The Problem with "It Runs Fast on My Machine"

When two programmers debate whose solution is better, the argument often devolves into: "Mine ran in 0.3 seconds." But that's meaningless. Your colleague might have a faster CPU. The input might be small. The test might have been run under special conditions.

We need a universal, hardware-independent way to describe how fast an algorithm is. That's where time complexity and Big O notation come in.

---

What Is Time Complexity?

Time complexity describes how the runtime of an algorithm grows as the size of the input grows.

We don't measure actual seconds. We count the number of basic operations — comparisons, assignments, additions — in terms of the input size n.

For example, if an algorithm does 3n + 5 operations for an input of size n, we say its time complexity is roughly O(n) — linear.

---

Big O Notation: The Language of Efficiency

Big O (written O(...)) describes an upper bound on an algorithm's growth rate. It tells you the worst case: no matter what, this algorithm will take at most this many steps.

The key rules of Big O:

1. Drop constants — O(2n) becomes O(n). We care about growth rate, not exact counts.
2. Drop lower-order terms — O(n² + n) becomes O(n²). At large n, the dominant term wins.
3. Different inputs get different variables — If a function loops over array A (size a) and array B (size b), it's O(a + b), not O(n²).

---

The Big O Hierarchy (From Best to Worst)

Notation	Name	Example
O(1)	Constant	Array index access
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n log n)	Linearithmic	Merge sort, heap sort
O(n²)	Quadratic	Bubble sort, nested loops
O(n³)	Cubic	Triple nested loops
O(2ⁿ)	Exponential	Recursive Fibonacci (naive)
O(n!)	Factorial	Brute-force permutations

As inputs grow, the difference between these complexities becomes enormous. For n = 1,000:

• O(log n) → ~10 operations
• O(n) → 1,000 operations
• O(n²) → 1,000,000 operations
• O(2ⁿ) → 10^301 operations (the universe would end first)

---

O(1) — Constant Time

An algorithm runs in constant time when its number of operations doesn't change with input size.

def get_first(arr):
    return arr[0]  # Always 1 operation, no matter the array size

Accessing an element by index in an array is O(1). It doesn't matter if the array has 10 elements or 10 billion — the computer jumps directly to that memory address.

---

O(n) — Linear Time

An algorithm runs in linear time when the number of operations scales directly with input size.

def linear_search(arr, target):
    for element in arr:          # n iterations in the worst case
        if element == target:
            return True
    return False

If the array doubles in size, the loop takes twice as long. Classic linear time.

---

O(n²) — Quadratic Time

Quadratic time typically comes from nested loops.

def has_duplicates(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):   # Nested loop → O(n²)
            if arr[i] == arr[j]:
                return True
    return False

If n = 100, this does ~5,000 comparisons. If n = 1,000, it does ~500,000. Quadratic algorithms become very slow for large inputs.

---

O(log n) — Logarithmic Time

Algorithms that halve the search space on each step are logarithmic.

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

Binary search on 1,000 elements takes at most ~10 steps. On 1,000,000 elements, at most ~20 steps. That's the power of logarithmic complexity.

---

Calculating Big O: Step-by-Step

Rule 1 — Single loops are O(n):

for i in range(n):
    do_something()   → O(n)

Rule 2 — Nested loops multiply:

for i in range(n):
    for j in range(n):
        do_something()  → O(n × n) = O(n²)

Rule 3 — Sequential blocks add:

for i in range(n):     → O(n)
    ...
for j in range(n):     → O(n)
    ...
Total: O(n + n) = O(2n) = O(n)

Rule 4 — Halving loops are O(log n):

while n > 1:
    n = n // 2      → O(log n)

---

Space Complexity

Big O doesn't just apply to time — it applies to memory too.

Space complexity measures how much extra memory an algorithm uses as input grows.

def double_array(arr):
    result = []            # Creates a new array of size n → O(n) space
    for x in arr:
        result.append(x * 2)
    return result

An in-place algorithm that modifies the input without creating new data structures uses O(1) extra space.

---

Common Mistakes When Analyzing Big O

Mistake 1 — Including input size in space complexity.
Input always takes O(n) space. We measure the extra space the algorithm uses, not the storage of the input itself.

Mistake 2 — Assuming nested loops are always O(n²).
If the inner loop doesn't depend on the outer loop variable, it might still be O(n²), or it might be O(n × m) for different-sized inputs.

Mistake 3 — Forgetting recursion uses stack space.
A recursive function that calls itself n times uses O(n) stack space, even if each call does O(1) work.

---

A Quick Reference

O(1)       < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Constant     Log         Linear  N-Log-N      Quad     Exp      Factorial

When you write code, always ask: "What is the Big O of this?" It becomes second nature with practice.

---

Summary

• Time complexity measures how operations grow with input size — not actual time in seconds.
• Big O notation gives an upper bound, describing worst-case growth.
• Drop constants and lower-order terms.
• Common complexities from best to worst: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).
• Space complexity applies the same idea to memory usage.
• Nested loops multiply; sequential blocks add.

In the next post, we'll go deeper into the three types of asymptotic notations — Big O, Omega (Ω), and Theta (Θ).

---