Sorting, Searching, and Big-O Intuition

Why the same task can feel instant on ten items and freeze on ten million

Big Idea: An algorithm's speed depends less on the machine than on how its work grows as the input grows. Big-O notation describes that growth. A linear scan doubles its work when the data doubles; a binary search barely notices. Learning to read this growth lets you predict, before you run anything, which approach will still be fast at scale.

By the end you will be able to:

implement linear search and binary search and say when each applies,
write bubble sort and insertion sort and compare them to Python's built-in sort,
read the classes O(1), O(n), O(n log n) and O(n^2),
use timeit to turn theory into measured numbers,
choose the right tool by reasoning about growth, not guesswork.

1. Why input size is the thing that matters

Any code is fast on a tiny list. The interesting question is what happens as the input grows to thousands or millions of items. We measure an algorithm not in seconds (those depend on your CPU) but in the number of basic steps it performs as a function of the input size, which we call n.

If doubling n roughly doubles the steps, the growth is linear. If doubling n quadruples the steps, it is quadratic and will punish you at scale. Big-O notation keeps only the dominant term and drops constants, because at large n the dominant term decides everything.

We describe the worst case unless stated otherwise: the input that forces the most work. It is the honest promise an algorithm can make.

2. Linear search: check them one by one

Linear search walks the list from the start and compares each element to the target. It works on any list, sorted or not, because it makes no assumptions about order.

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i          # found: return its position
    return -1                 # not found

In the worst case the target is last (or missing) and we touch all n elements. That is O(n): double the list, double the work. On a million items a linear search may do a million comparisons.

Sorting, Searching, and Big-O Intuition