Time Complexity & the Class P

asymptotic growth

If you watch two saplings, the slightly taller one today tells you almost nothing about which will be the bigger tree in fifty years; what matters is how fast each keeps growing. Asymptotic growth is that long-run view applied to functions. It asks not 'how big is the running time at n = 10?' but 'how does the running time behave as n marches off toward infinity?' For deciding which algorithm wins on large problems, the eventual growth is the whole story and the early wobbles are noise.

This long-run view is exactly why big-O, big-Omega, and big-Theta are defined 'for all n greater than some n0': they describe behaviour out in the tail, ignoring what happens for small inputs. Asymptotically, growth rates form a strict pecking order, and lower-order terms simply vanish. For instance, n^2 grows faster than 100n + 50 eventually, even though 100n + 50 is larger for small n. Once n passes the crossover point, the higher-order term dominates forever, and the constants and additive terms become irrelevant to the comparison. That is the precise sense in which we say one algorithm 'beats' another.

Thinking asymptotically is liberating because it lets us compare methods without knowing the machine, the language, or the exact constants, and it is the reason a single curve like n log n can summarise an algorithm's destiny. But the same abstraction can mislead: 'eventually' may be a very large n. An O(n log n) method can lose to an O(n^2) method on small inputs if the first hides a big constant, which is why real engineering still measures, and why we will be careful when we equate asymptotic polynomial time with 'feasible'.

Compare T1(n) = 1000n and T2(n) = n^2. For n = 100, T1 = 100000 beats T2 = 10000? No: T1 = 100000 is larger. But for n = 1001 and beyond, T2 = n^2 overtakes T1 = 1000n forever, because the crossover is at n = 1000. Asymptotically, n^2 grows faster, so T2 is the worse algorithm at scale.

Below the crossover the smaller-growth function can be larger; past it, growth rate always wins.

'Asymptotic' means 'as n goes to infinity', so a faster-growing function can be smaller for small n; the crossover may sit at a large n that real inputs never reach.

Also called
asymptotic behaviourgrowth rateasymptotics漸近行為成長率