A new question on the same ladder
Every rung you have climbed so far asked one question: can this be done at all? A decidable language is one some Turing machine always settles with a definite yes or no; an undecidable one, like the halting problem, defeats every machine no matter how long it runs. That question is binary and timeless — it does not care whether the machine answers in a blink or after a billion years. From this rung on, the question changes. We now grant that a problem is solvable and ask the practical follow-up: how long does it take? A decider that always halts but takes longer than the age of the universe on a fifty-symbol input is, for any human purpose, no better than one that never halts.
So we need a way to measure the work a machine does, and the natural unit is already sitting in front of us. A Turing machine computes by repeating one tiny move — read the cell, write the cell, step the head — over and over until it halts. So we simply count the moves: the running time of a machine on a given input is the number of those steps it makes before halting. This step-counting is the raw material of time complexity, the study of how that count grows. It is honest because it ties the cost to the model we already trust: no wall clock, no hardware, just elementary moves of the head.
Step count alone is a useless number
Here is the catch: "it took 4000 steps" tells you nothing on its own. Four thousand steps to sort three names is a catastrophe; four thousand to sort a million names is a miracle. The same machine takes wildly different amounts of work depending on how much input it was handed. So a single number is meaningless. What we actually want is a function — a rule that says, for an input of this size, the machine takes at most this many steps — so we can see how the cost scales as the input grows. Time complexity is never one number; it is always a function of the input size.
That forces a precise question: what is the size of an input? The convention is the one already baked into everything you have done: an input is a string, and its size is its length — the number of symbols in it — written n. A graph with five vertices and seven edges, a number to be factored, a list to be sorted: each must first be written down as a string over some alphabet Sigma (Σ), and n is how long that string is. We measure cost against this n. Time complexity, then, is a function T(n): the worst number of steps the machine takes on any input of length n.
Whose case? The worst one
Even for a fixed length n there are many different inputs, and they need not all cost the same. Think of searching a list of n names for one target. If your target happens to sit first, you find it in one step; if it is last, or missing, you scan all n. Same n, two very different step counts. So which do we report? The discipline of this field is to report the worst case: T(n) is the largest number of steps the machine takes over all inputs of length n. We deliberately assume the most unlucky input possible.
Why be so pessimistic? Two honest reasons. First, a worst-case bound is a guarantee: if the machine never takes more than T(n) steps on the unluckiest input, then it never takes more than T(n) on any input — the promise holds no matter what arrives. An average-case figure, by contrast, depends on assuming inputs are drawn from some distribution, and real inputs rarely oblige; the worst case needs no such assumption. Second, an adversary who feeds your program inputs on purpose will hunt for exactly the bad case, so for anything where reliability matters, the worst case is the number you must live by.
Linear search for a target in a list of n names input: [ N1 N2 N3 ... Nn ] and a target T step: compare T to N1, then N2, ... stop at the first match BEST case target is N1 -> 1 comparison TYPICAL target somewhere middle -> about n/2 comparisons WORST case target is Nn OR absent -> n comparisons We report the WORST case: T(n) = n comparisons. Same n, three very different costs -- the worst one is the guarantee.
Smoothing the count: we care about growth, not grit
Even a clean worst-case T(n) is messier than we want. The exact step count depends on fussy details: whether your machine has one tape or two, whether a comparison costs three head-moves or five, whether you count a tidy-up pass at the end. Tally all that and you might get T(n) = 5n + 17 on one machine and T(n) = 3n + 40 on another — for the very same task. Those constants and low-order terms are real, but they are accidents of the model and the bookkeeping, not of the problem. Pinning them down precisely would chain our answer to one particular machine, which is exactly what we do not want.
The way out is to look only at how T(n) grows as n gets large, ignoring constant factors and lower-order terms. On that lens, 5n + 17 and 3n + 40 are the same: both grow linearly, like n. This is the idea behind big-O notation — we say both algorithms run in O(n) time, meaning their step count is at most some constant times n once n is big enough. Big-O is the topic of the very next guide, so we will not formalise it here; for now hold the intuition: it is an upper bound on the worst-case growth rate, a way of saying "in the long run this scales like n (or n^2, or 2^n)" while throwing away the constants that depend on the machine.
Why this scaffolding is the whole point
It may feel like a lot of throat-clearing — count steps, measure against length n, take the worst case, smooth away constants. But these four choices are exactly what let us draw a meaningful line between problems we can solve fast and ones we cannot. Once T(n) is a clean function of n, we can sort algorithms onto a ladder of growth rates: constant, logarithmic, linear, n log n, quadratic n^2, cubic n^3, and far up the ladder the dreaded exponential 2^n. A few rungs apart these look similar; stretch n out and the gulf is staggering. At n = 50, an n^3 algorithm finishes in 125000 steps while a 2^n algorithm needs over 10^15 — the difference between instant and never.
That gulf is why we draw the headline boundary at polynomial growth — any T(n) bounded by n raised to a fixed power, like n, n^2, or n^100. Polynomial running time is the working definition of a tractable (efficiently solvable) problem, and exponential time the mark of intractability. The next three guides build straight on the machinery you just set up: guide 2 makes big-O, big-Omega and big-Theta precise and lays out the growth ladder; guide 3 defines the class P — the problems decidable in polynomial time on a deterministic machine; guide 4 shows why P is robust across reasonable models; and guide 5 asks the honest question of whether "polynomial" really equals "feasible."
One last alignment keeps this consistent with everything before. Throughout, we phrase problems the same way the whole subject does: as yes/no questions, a language of the inputs whose answer is yes. "Is this graph connected?", "Is this number prime?", "Is this list sorted?" — each is a membership test, and the machine's job is to decide it. Measuring how the step count for that decision grows with n, in the worst case, up to constants, is the entire programme of this rung. Everything that follows is just naming and exploring the regions of that growth.