Comparing Time Complexities Means Comparing Growth

Growth rate, not the current step count, determines the asymptotic order

Consider the seven routines applied to the array [7, 2, 9, 1, 5, 8, 3, 6]. Their supplied step-count functions are 20, 10 * log2(n), 100 * n, n * log2(n), n^2, 2^n, and n!. The asymptotic ordering asks how each function grows as n increases, not which function currently has the smallest numerical value.

1. 120, constant growth
2. 210 * log2(n), logarithmic growth
3. 3100 * n, linear growth
4. 4n * log2(n), linearithmic growth
5. 5n^2, quadratic growth
6. 62^n, exponential growth
7. 7n!, factorial growth

The constants 10 and 100 change the step counts, but they do not change the growth class. Multiplying a function by a fixed number only stretches its values. The same idea places n * log2(n) after linear growth and before quadratic growth, while exponential and factorial growth eventually pull far away from every polynomial function.

At n = 8, a worse growth class can still do less work

For the given array, n = 8 and log2(8) = 3. Substituting those values gives a very different picture from the asymptotic ordering. The quadratic routine takes 64 steps, while the linear routine 100 * n takes 800 steps. Quadratic growth is worse in the long run, but its smaller constant lets it do less work at this input size.

This is why you cannot use asymptotic order as a promise about every individual input. At n = 8, n * log2(n) takes 24 steps, which is fewer than the constant-looking 20 only if the supplied models are compared literally? No, 24 is greater than 20. The point is that growth classes describe what happens as inputs scale, while concrete constants and the current n determine the result at one size.

Scaling the same input exposes the crossover point

Compare only 100 * n and n^2 while the input length grows from 8 toward 100. At n = 8, the linear routine takes 800 steps and the quadratic routine takes 64, so n^2 is smaller. The two expressions are equal when 100 * n = n^2. For positive n, dividing by n gives 100 = n, so the crossover point is n = 100.

At n = 100, both routines take 10,000 steps. After n becomes larger than 100, n^2 grows faster than 100 * n, so the linear routine becomes the smaller one. At n = 128, 100 * n takes 12,800 steps while n^2 takes 16,384. The better growth rate wins only after the crossover, not automatically at every smaller input.

100 * n = n^2

A complexity comparison predicts scalability, not exact runtime

The seven step-count functions let you compare long-run growth, but they do not act like stopwatch readings. A routine with fewer modelled steps may still take longer because each step does more work. A routine with a larger constant may be carefully implemented, while another routine may spend time on extra operations that the simple model does not count.

Hardware also changes measured time. Processor speed, compiler choices, memory access, caching, and the cost of moving data can all affect the result. Space complexity matters too: a routine that uses more memory can trigger slower memory access or allocation costs even when its time growth class looks attractive.

Asymptotic notation remains useful because it gives you a common basis for scalability. The functions 2^n and n! eventually outgrow the polynomial functions, and n^2 eventually outgrows 100 * n. Those statements remain true even when constants, hardware, and memory effects make a different routine faster for the input sizes you actually measure.