time complexity

Time complexity answers one practical question: as the input gets bigger, how does the running time grow? Instead of timing your program with a stopwatch — which depends on your laptop, the language, even how busy the machine is — we count the number of basic steps the algorithm performs as a function of the input size, usually called n. Stopwatch seconds change from machine to machine; the shape of the growth does not. That shape is what we care about, because it predicts what happens when n is a thousand, a million, a billion.

We describe that shape with Big-O notation, keeping only the dominant term and dropping constants. Scanning a list to find the largest item touches every element once, so it is O(n) — linear: double the input, roughly double the work. Comparing every pair of items is O(n^2) — quadratic: double the input and the work quadruples. Binary search halves the search space each step, so it is O(log n) — barely grows at all. And a lookup that takes the same time no matter how big the collection is, like a good hash table, is O(1) — constant.

The reason this matters is brutal arithmetic. At n = 1,000,000 an O(n) algorithm does about a million steps; an O(n^2) one does a million million — a trillion — which can turn a one-second task into one that runs for days. So the first question a careful programmer asks about an algorithm is not 'does it work?' but 'how does its time scale?' We usually report the worst case (the slowest the algorithm can be over all inputs of size n), because it is the guarantee you can rely on, though average-case and amortized analyses tell the rest of the story.