Big O Notation

Big O notation is a way of describing the performance of a function without using time. Rather than timing a function from start to finish, Big O describes how the time grows as the input size increases. It is used to help understand how programs will perform across a range of inputs.

O(n) - Linear Time

Analogy: Reading a book page by page. If the book has 10 pages, it takes some time. If it has 100 pages, it takes 10 times as long.

In code, this usually happens with a simple loop. As the input n grows, the time taken grows linearly.

def print_all_items(items):
    for item in items:
        print(item)

O(1) - Constant Time

Analogy: Picking the first book off a shelf. It doesn't matter if there are 10 books or 10,000 books on the shelf, grabbing the first one takes the same amount of time.

In code, this is accessing an array by index or doing a simple math operation.

def get_first_item(items):
    return items[0]

O(n²) - Quadratic Time

Analogy: Imagine a square grid of size n by n. To fill every cell in the grid, you have to visit n rows and n columns. That's n * n operations.

In code, this happens with nested loops. For every item in the list, we loop through the entire list again. Watch how the grid fills up below. As n grows, the area of the square grows much faster than the side length.

def print_grid(n):
    for row in range(n):
        for col in range(n):
            print(row, col)

O(log n) - Logarithmic Time

Analogy: The "Guess Who" game or looking up a word in a dictionary. You open the book to the middle. If the word you're looking for is alphabetically after, you can completely tear out and throw away the first half of the book.

You keep cutting the problem in half. Even with a dictionary of 1 million words, you only need to cut it in half about 20 times to find any word.

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