Growth Rate Comparisons: How to Order Functions Step by Step

Comparing n log n, sqrt(n), and 2^n can look like a substitution exercise. Constants, logarithm bases, disguised forms, and small inputs soon make a value table misleading. Separate one value from long-run growth, normalise each expression, apply a valid comparison, and then check the result with exact numbers. Prove the eventual ordering before trusting the snapshot each time.

Growth rate means what happens eventually

A cost function counts a chosen basic operation in terms of input size n. The claim f(10) > g(10) compares two values at one input. A growth-rate claim says which function becomes larger and stays larger as n increases.

Take f(n)=100n and g(n)=n^2. At n=10, f(10)=1000 while g(10)=100. They are equal at n=100. At n=1000, f(1000)=100000 but g(1000)=1000000. The linear function wins for some practical inputs, although the quadratic has the higher growth rate.

Here, "eventually" means there is a threshold n_0 after which the ordering holds for every larger valid n. Constants still matter in exact running time. We ignore them only while identifying the asymptotic class. The GATE category is a broader subject and practice hub for applying this distinction.

Use bounds and ratios instead of guessing from shape

O(g(n)) is an eventual upper bound, Omega(g(n)) an eventual lower bound, and Theta(g(n)) both. The stricter statement f=o(g) says that f grows more slowly than g. The notation f(n)=O(g(n)) is set membership, not equality between the two functions.

For eventually positive functions, examine lim f(n)/g(n). A limit of 0 gives f=o(g). A finite positive constant gives f=Theta(g). Infinity means f grows strictly faster. If the limit does not exist, return to inequalities or another test.

Three checks show the method:

• (3n^2+7n+4)/n^2 = 3+7/n+4/n^2, which tends to 3, so 3n^2+7n+4=Theta(n^2).

• (n log_2 n)/n^(3/2) = log_2 n/sqrt(n), which tends to 0.

• 2^n/n^5 tends to infinity. A finite table may illustrate this result, but cannot prove it.

Build and normalise the standard hierarchy

For fixed k>1, 0<epsilon<1, and c>1, the eventual ladder is:

1 < log log n < log n < (log n)^k < n^epsilon < n < n log n < n^2 < c^n < n! < n^n

This is strict eventual growth, not numerical < at every small n. It moves successively from constants through nested logarithms and polynomials to exponential and factorial forms. Normalise a disguised expression before placing it. With base-2 logs and n>1:

• log_2(n^4)=4log_2 n

• 2^(log_2 n)=n

• n^(1/log_2 n)=2

Also, log_a n=log_b n/log_b a. Changing a fixed valid log base introduces a constant factor, so it does not change the asymptotic class. Sorting Algorithms: Complexity and Comparison applies this hierarchy when comparing n log n and n^2 algorithms.

Order eight disguised functions

For n>1, rewrite before comparing.

The eventual order is A < B < C < D < E < F < G < H.

At log_2 256=8, the numerical snapshot is A < D < B=E < F < C < G < H. In particular, C(256)=512 while D(256)=16. That reversal does not refute the proof. At n=2^64, C=64^3=262144, while D=2^32=4294967296, so the eventual relation is visible.

Separate equal growth classes from equal values

Let p(n)=6n^2+n and q(n)=0.25n^2+1000000. Their ratio tends to 6/0.25=24, so both are Theta(n^2), although they are not equal. At n=100, p=60100 and q=1002500. At n=10000, p=600010000 and q=26000000. The larger function changes, but the class does not. That is what sharing a class means.

Similarly, log_2(n!)=Theta(n log n), not an exact equality. Since n! <= n^n, log_2(n!) <= n log_2 n. For even n, the largest n/2 factors are at least n/2, so log_2(n!) >= (n/2)log_2(n/2). At n=8, 8!=40320, log_2(40320) is about 15.30, and 8log_2 8=24.

Avoid the transformations and crossover traps

Compare r(n)=n^(log_2 n) with s(n)=2^n by taking base-2 logs. This preserves order because logarithm is increasing. The transformed functions are (log_2 n)^2 and n. Since (log_2 n)^2=o(n), we get r=o(s).

At n=16, 16^4=65536 and 2^16=65536, a deceptive tie. At n=32, 32^5=33554432, while 2^32=4294967296. Equality at one input is not equality of growth classes.

Keep four other traps separate:

• A larger coefficient does not create a higher asymptotic class.

• A different fixed log base changes exact values, not Theta.

• O(n^2) does not imply Theta(n^2). For example, 3n+2 is also O(n^2).

• Parentheses matter: 2^(log_2 n)=n, but (2^n)log_2 n is a different function.

Recognise the common exam-style question forms

Common forms ask you to order functions, test an O or Theta claim, rewrite expressions, apply a limit, or derive costs from code.

Use these answer checks:

1. 3n+2=O(n^2) is true, but 3n+2=Theta(n^2) is false.

2. If an outer loop takes i=1,2,4,...,n and an inner loop performs n operations, the cost is Theta(n log n). At n=16, five outer values times 16 gives 80 operations.

3. log_2(n!) and n log_2 n share a Theta class, but are not equal.

Algorithm Analysis Basics starts from exact operation counts and turns those counts into asymptotic classes. The comparison here starts from closed-form functions: normalise them, prove their eventual order, and treat numerical values only as checkpoints.

The short version and the next action

Use this five-step chain:

1. Identify the input variable.

2. Normalise logs, powers, and factorials.

3. Decide whether the question asks for one value or eventual growth.

4. Apply a ratio or inequality.

5. Use a numerical value only as a sanity check, never as the proof.

Now rebuild the eight-row table without notes. Reproduce A < B < C < D < E < F < G < H, then explain why C(256)=512 > D(256)=16 does not contradict C=o(D). For a broader structured route, see GATE Guidance by Sanchit Sir. For timed practice, use the GATE Test Series.