The question worth asking
In the earlier rung you learned to count an algorithm's cost in basic steps rather than seconds, using the machine-independent cost model. That left us with an honest number — say, this method does 5n + 3 steps on an input of size n — but it also left us drowning in detail. Is the 5 important? Is the +3? If a friend's method does 7n + 100 steps instead, which one should we prefer, and for which inputs? Asymptotics is the discipline that answers these questions by deciding, deliberately, what to throw away.
The key move is to stop asking "how long does it take on this input?" and start asking "how does the cost grow as the input size n grows without bound?" That shift is what asymptotic analysis is about. It is the difference between timing one race and predicting who wins every future race as the track gets longer and longer. We care about the trend, because the trend is what survives a change of computer, language, or input.
Throwing away constant factors
The first thing we discard is the constant factor — the multiplier out front. Whether a method does 5n steps or 100n steps, both grow in straight-line proportion to n: double the input and the cost doubles. We lump them together and call both "order n", or linear. The justification is concrete: a faster CPU, a better compiler, or a lower-level language can each speed up every step by some fixed factor, and that factor multiplies the whole count. So the leading constant is a property of your machine and your craftsmanship, not of the algorithm's idea.
This is exactly why a textbook can claim "merge sort runs in time proportional to n log n" without naming a single computer, and have it stay true for decades on machines no one had imagined. The unknown "steps per second" of any particular machine is just another constant, and we have agreed in advance not to track constants. That agreement is what makes the conclusion portable.
Throwing away low-order terms
The second thing we discard is the low-order terms — the smaller pieces of a sum. Suppose a careful count gives n^2 + 3n + 7 steps. As n grows, the n^2 part takes over and the rest fades into the background. The reason is arithmetic, not hand-waving: at n = 1000, the n^2 term is 1,000,000 while 3n + 7 is barely 3,007 — about three-thousandths of the total. At n = 1,000,000 the low-order terms are utterly invisible. So we report n^2 and drop the rest, because what we kept is the part that actually decides the growth.
Put the two moves together and a long, fussy expression collapses to its essence. A cost of 4n^2 + 100n + 9000 first loses its low-order terms (100n and 9000 vanish next to n^2), then loses its leading constant (the 4 is absorbed), leaving simply n^2. The vivid mental picture: as n marches to the horizon, only the single fastest-growing term still casts a shadow, and even that term's coefficient is washed out. What remains is the order of growth — the shape, not the size.
- Write the cost out as a sum of terms, e.g. 4n^2 + 100n + 9000.
- Find the single fastest-growing term; here that is the n^2 term.
- Delete every slower term — they become a vanishing fraction for large n.
- Drop the leading constant; what is left, here n^2, is the order of growth.
Why this is the honest comparison
Stripping cost down to its order of growth is what lets us say something true that no benchmark can: a method that grows like n^2 will eventually lose to one that grows like n log n, no matter whose laptop runs them. The gap widens without bound, so beyond some input size the slower-growing method wins and never gives the lead back. This is the payoff of the growth-rate hierarchy — once you know two methods sit on different rungs, you know who wins the large-n race before you run anything.
But here is the part too many people skip. Because we threw away the constants and the low-order terms, asymptotics describes scaling, not a verdict at every size. For small n, the very details we discarded can completely reverse the ranking. An O(n log n) method can genuinely lose to an O(n^2) method when n is small, if the n^2 method's hidden constant is tiny — this is the hidden-constant pitfall, and it is why real sorting libraries fall back to simple quadratic-ish sorts for short lists. "Eventually" is doing real work in every asymptotic claim.
So hold the order of growth as exactly what it is: a promise about large inputs only — this is the large-n caveat. It does not say the "better" method wins at n = 5, or even n = 50; the crossover point can be surprisingly large. Treat the order of growth as a prediction about scaling, and when the actual input size matters, measure rather than assume.
Where the growth comes from: loops
Concretely, the order of growth is usually born in an algorithm's loops, and you can often read it off without summing anything exactly. The rule of thumb is simple: count how many times the innermost work runs. A single loop that touches each of n items once does work proportional to n — linear, Theta(n) — because the body runs n times and each run costs a constant we are allowed to ignore. The constant per iteration disappears into the leading factor we already agreed to drop.
Nest one loop inside another and the counts multiply. If the outer loop runs n times and, for each of those, the inner loop also runs n times, the body runs n times n equals n^2 times — quadratic. That is the heart of the famous double loop: comparing every pair of n items does about n^2 work. Even when the inner loop's length varies, the same multiplying intuition holds and the sum still lands on the same order; for example an inner loop that runs i times as the outer index i climbs from 1 to n does 1 + 2 + ... + n = n(n+1)/2 steps, which is (1/2)n^2 + (1/2)n — and after dropping the constant and the low-order term, that is plain Theta(n^2).
for i = 1 .. n: # outer runs n times
for j = 1 .. n: # inner runs n times each
do_constant_work # body runs n * n = n^2 times -> Theta(n^2)Notice how naturally the two discards reappear here. We never wrote down the cost of one loop body in nanoseconds (that constant is dropped), and when the exact count came out as (1/2)n^2 + (1/2)n we kept only the n^2 (low-order term dropped). The loop structure hands you the order of growth almost for free — which is exactly the skill the rest of this rung sharpens, from the formal meaning of Big-O to reading the running time off real code.