DSA Big O Notation

Before diving into data structures and algorithms, it is essential to understand how to measure their efficiency. Two programs might both solve the same problem correctly, but one might be significantly faster or use far less memory than the other. Complexity Analysis provides a standardized way to compare and evaluate the performance of algorithms.

The most widely used tool for this is Big O Notation.

What is Big O Notation?

Big O Notation is a mathematical notation used to describe the worst-case performance of an algorithm as the input size grows. It answers the question: "How does the runtime (or memory usage) of this algorithm grow as the data gets larger?"

The letter O stands for "Order of," meaning the order of growth. The variable n typically represents the size of the input.

Why Worst-Case Analysis?

Imagine looking for a specific name in a phone book by checking every name one by one. In the best case, the name is on the first page. In the worst case, it is on the last page. Big O focuses on the worst case so that performance expectations are realistic and safe for large inputs.

Common Big O Complexities

O(1) — Constant Time

The algorithm takes the same amount of time regardless of input size. It does not matter whether there are 10 items or 10 million — the operation is always equally fast.


# Accessing a list element by index — always one step
numbers = [10, 20, 30, 40, 50]
print(numbers[2])   # Output: 30
# No matter how long the list is, index access is instant

O(n) — Linear Time

The runtime grows in direct proportion to the input size. If there are twice as many items, the algorithm takes roughly twice as long.


# Checking each item in a list — one pass through
def find_item(lst, target):
    for item in lst:
        if item == target:
            return True
    return False

print(find_item([3, 7, 1, 9, 4], 9))   # Output: True
# As the list grows, the search time grows equally

O(n²) — Quadratic Time

The runtime grows proportionally to the square of the input size. This typically occurs when there are two nested loops, each iterating over the input.


# Printing all pairs from a list — nested loops
def print_pairs(lst):
    for i in lst:
        for j in lst:
            print(i, j)

print_pairs([1, 2, 3])
# For 3 items: 9 pairs
# For 10 items: 100 pairs — grows quickly

O(log n) — Logarithmic Time

The runtime grows very slowly even as input size increases dramatically. Each step eliminates a large portion of the remaining data. Binary search is a classic example — it cuts the search space in half with each step.


# Binary search on a sorted list
def binary_search(lst, target):
    left, right = 0, len(lst) - 1
    while left <= right:
        mid = (left + right) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

sorted_list = [2, 5, 8, 12, 16, 23, 38]
print(binary_search(sorted_list, 23))   # Output: 5

O(n log n) — Linearithmic Time

This is common in efficient sorting algorithms like Merge Sort and Quick Sort. It is better than O(n²) but slower than O(n). For large datasets, this is often the best achievable complexity for comparison-based sorting.

O(2ⁿ) — Exponential Time

The runtime doubles with each additional input element. Algorithms with this complexity become unusable very quickly as input grows. Recursive Fibonacci without optimization is a classic example.


# Naive recursive Fibonacci — exponential time
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))   # Output: 55
# Works fine for small n, but extremely slow for n = 50

Visualizing Growth Rates

To understand the difference in complexities, consider how many operations each requires for an input of size 16:

  • O(1) — 1 operation
  • O(log n) — 4 operations
  • O(n) — 16 operations
  • O(n log n) — 64 operations
  • O(n²) — 256 operations
  • O(2ⁿ) — 65,536 operations

The difference becomes even more dramatic as n grows to 1,000 or 1,000,000.

Space Complexity

Big O is also used to analyze memory usage. This is called space complexity. An algorithm might be fast but use large amounts of memory, which can be a problem in memory-constrained environments.

Example


# O(n) space complexity — storing all results
def double_all(lst):
    result = []
    for item in lst:
        result.append(item * 2)
    return result

# The result list grows with input size — O(n) space used

Simplification Rules in Big O

Rule 1: Drop Constants

O(2n) simplifies to O(n). Constants are ignored because they do not affect how the function grows.

Rule 2: Drop Non-Dominant Terms

O(n² + n) simplifies to O(n²). As n grows large, the smaller term becomes insignificant.

Rule 3: Different Variables for Different Inputs

If a function iterates over two separate arrays of sizes m and n, the complexity is O(m + n), not O(n²).


# Two separate loops — O(a + b), not O(n^2)
def combined(a, b):
    for item in a:
        print(item)
    for item in b:
        print(item)

Key Points

  • Big O Notation measures how an algorithm's runtime or memory usage grows with input size.
  • It focuses on worst-case scenarios to set realistic performance expectations.
  • Common complexities from fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
  • Space complexity follows the same notation but measures memory usage instead of time.
  • Constants and non-dominant terms are dropped when expressing Big O.
  • Understanding Big O is essential before studying specific data structures and algorithms.
Previous lessons
Back to courses
Next lessons

Leave a Comment