Big O Notation: Measuring Code Efficiency

Big O notation describes how an algorithm's running time or memory use grows as the size of its input grows, independent of hardware or language.

Two Chefs, One Kitchen

Imagine two chefs working in a restaurant kitchen. Both need to locate ingredients during a busy dinner service.

Chef A has a completely unorganized pantry. Flour could be anywhere. Every time a recipe calls for cumin, she scans every single shelf from left to right until she finds it.

Chef B organized the pantry before service: spices alphabetically on the top shelf, grains by weight on the middle shelf, oils on the bottom shelf. He walks straight to where an ingredient must be.

On a quiet Tuesday with 10 ingredients, both chefs manage fine. On a Saturday night with 500 ingredients, Chef A is a bottleneck. The restaurant grinds to a halt waiting for her to find the cardamom.

Big O notation is the tool for measuring this difference not in milliseconds, but in how the time grows as the pantry gets larger.

What Big O Actually Measures

Big O notation describes the relationship between input size and resource usage (time or memory) as the input grows toward infinity.

Two critical rules:

1. We measure worst case performance (Chef A searching for the last item on the shelf)
2. We care about scaling behavior, not the exact number of steps

Big O does not tell you how fast your code runs on your specific machine. It tells you how your code will behave as the problem gets bigger.

The letter n always represents the size of the input. A function that processes a list of 1,000 items has n = 1000.

The Six Complexities You Must Know

Growth Rate Comparison

Here is exactly how these complexities scale as n grows. These numbers make the differences visceral:

An O(n²) algorithm that takes 1 second for 1,000 items will take over 11 days for 1,000,000 items.

Python Code Examples for Each Complexity

O(1) Constant Time

def get_first(arr):
    return arr[0]        # One operation, always

def dict_lookup(data, key):
    return data[key]     # Hash table: instant regardless of size

# Sample input
numbers = [42, 7, 15, 99, 3]
print(get_first(numbers))   # Output: 42

scores = {"Alice": 95, "Bob": 87, "Carol": 92}
print(dict_lookup(scores, "Carol"))  # Output: 92

Why O(1)? The operation does not depend on how large arr or data is. Whether there are 5 items or 5 million, the work is identical.

O(log n) Logarithmic Time

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2   # Check the middle element
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1          # Discard the left half
        else:
            right = mid - 1         # Discard the right half
    return -1

sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(sorted_list, 23))   # Output: 5 (index)
print(binary_search(sorted_list, 99))   # Output: -1 (not found)

Why O(log n)? Each step cuts the remaining search space in half. For 1,024 items, it takes at most 10 comparisons (2¹⁰ = 1,024). For 1,048,576 items, just 20 comparisons.

O(n) Linear Time

def find_max(arr):
    max_val = arr[0]
    for item in arr:           # Visits every element once
        if item > max_val:
            max_val = item
    return max_val

def linear_search(arr, target):
    for i, item in enumerate(arr):   # Worst case: check all n items
        if item == target:
            return i
    return -1

numbers = [34, 7, 23, 32, 5, 62]
print(find_max(numbers))              # Output: 62
print(linear_search(numbers, 23))     # Output: 2

Why O(n)? The loop runs once per element. Double the input size, double the work. Simple and direct.

O(n²) Quadratic Time

def has_duplicate(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):   # Nested loop: n × n comparisons
            if arr[i] == arr[j]:
                return True
    return False

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

items = [3, 1, 4, 1, 5, 9, 2, 6]
print(has_duplicate(items))               # Output: True
print(bubble_sort([64, 34, 25, 12, 22]))  # Output: [12, 22, 25, 34, 64]

Why O(n²)? For every one of the n elements in the outer loop, the inner loop runs up to n times. Total operations: approximately n × n = n².

The Three Rules for Calculating Big O

Rule 1: Drop the constants

def two_loops(arr):
    for x in arr: print(x)    # O(n)
    for x in arr: print(x)    # O(n)
    # Total: O(2n) → simplified to O(n)

We write O(n), not O(2n). Constants do not affect the shape of growth.

Rule 2: Drop lower order terms

def mixed(arr):
    for x in arr:                   # O(n)
        for y in arr: print(x, y)   # O(n²)
    # Total: O(n² + n) → simplified to O(n²)

As n grows, n² overwhelms n completely. The lower term disappears.

Rule 3: Worst case wins

def search(arr, target):
    for item in arr:           # Best case: O(1) if target is first
        if item == target:     # Worst case: O(n) if target is last
            return True
    return False

Big O always refers to the worst case unless explicitly stated otherwise.

Space Complexity: Memory Matters Too

Big O applies to memory usage, not just time.

# O(1) space — uses same memory regardless of input size
def sum_list(arr):
    total = 0
    for x in arr:
        total += x
    return total

# O(n) space — creates a new list as large as the input
def double_all(arr):
    return [x * 2 for x in arr]   # New list of n elements

# O(n) space — call stack grows with n during recursion
def countdown(n):
    if n == 0: return
    countdown(n - 1)   # Each call adds a frame to the stack

A function can have excellent time complexity but poor space complexity always consider both.

The Common Mistake: Trusting Hardware Speed

Developers sometimes say, "My computer is fast, so O(n²) is fine." This is one of the most dangerous assumptions in software engineering.

A modern laptop might execute 100 million simple operations per second. Here is what that means at scale:

A 10x increase in data turned a 10-second process into a 28-hour process. Hardware cannot save bad complexity choices.

Key Takeaways

• Big O describes how resource usage scales with input size, not exact execution time
• Always analyze worst case unless told otherwise
• Drop constants and lower order terms only the dominant term matters
• The practical hierarchy: O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ)
• Space complexity is equally important always consider both time and memory
• A good data structure choice can reduce an O(n) search to O(1) without changing the algorithm at all

In the next lesson, you will apply this framework immediately as you study arrays the most fundamental data structure in all of computing.