Big-O Notation — Measuring Growth Rate

Build the mental model

Big-O notation describes how an algorithm's cost — time or memory — grows as its input size n grows, not how many literal seconds it takes on your laptop. That distinction matters because raw seconds depend on CPU speed, language, and today's system load, none of which tell you anything about how the algorithm will behave when n doubles or grows a thousandfold; growth rate is the property that actually predicts scaling. Big-O also deliberately ignores constant factors and lower-order terms: an algorithm that does 3n+100 operations and one that does n operations are both O(n), because past a certain n the constant multiplier stops mattering compared to how steeply the curve rises. The common classes, ordered from best to worst growth, are O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, and O(n²) quadratic. To estimate a function's complexity, count nested loops and lookups: a single pass over n items is O(n); a loop inside a loop over the same n is O(n²); a dictionary or set lookup, regardless of how many items it holds, is O(1).

Connect it to a real scenario

When the Tutorial Platform's search feature ranks results, the difference between an O(n log n) sort and an accidental O(n²) sort (say, from a naive bubble sort or repeated linear re-scans) is the difference between ranking a few hundred lessons instantly and freezing the page once the catalog grows to thousands. Recognizing complexity classes lets you predict, before you ever run a profiler, which implementation choice — a dict lookup for slug-to-content versus a linear scan through every lesson record — will keep the platform responsive as content keeps growing.

Big-O measures how cost grows with input size n, not literal runtime in seconds
Constant factors and lower-order terms are ignored — O(n) covers both n and 3n+100 operations
Common classes from best to worst: O(1), O(log n), O(n), O(n log n), O(n²)

Try the working example

python

def find_max_linear(numbers):
    # Single pass over all n items -> O(n): cost grows directly with input size
    current_max = numbers[0]
    for num in numbers:
        if num > current_max:
            current_max = num
    return current_max

def lookup_price(catalog, item_name):
    # dict lookup by key -> O(1): cost stays flat no matter how big catalog gets
    return catalog.get(item_name)

numbers = [4, 19, 2, 77, 5, 42]
catalog = {'pen': 500, 'book': 3500, 'bag': 12000}

print('Max (O(n) scan):', find_max_linear(numbers))
print('Price lookup (O(1)):', lookup_price(catalog, 'book'))

You should see

Prints 'Max (O(n) scan): 77' from scanning every element once, and 'Price lookup (O(1)): 3500' from a single dict lookup regardless of catalog size.

5-minute try-it

Add a function that checks whether a target value exists in `numbers` using a for-loop, and one that checks membership in a Python set built from the same numbers. Time both with `numbers` scaled up to 100,000 items and compare.

One important caution

Benchmarking two implementations only on tiny input (say, 5 items) and concluding they perform the same — an O(n) and O(1) approach look identical until n is large enough for the growth-rate gap to show.

Confusing 'this function has fewer lines of code' with 'this function is faster' — a short one-liner that hides a nested loop can still be O(n²), while a longer function using a dict can be O(n).

Wikipedia — Big O notation — Data Structures & Algorithms