Comparing Growth Rates Using Limits

One standard method to compare function sizes is to evaluate:

${\lim }_{n\to \mathrm{\infty }}\frac{f(n)}{g(n)}$

The value of this limit determines the relative growth of the functions.

---

Case 1: Limit Equals Zero

If:

$\lim_{n\to\infty}\frac{f(n)}{g(n)}=0$

then:

• $f(n)$ grows slower than $g(n)$
  
• $f(n)=o(g(n))$
  

---

Example

Compare:

$$f(n)=n$$

and

$$g(n)=n^2$$

Compute:

$\lim_{n\to\infty}\frac{n}{n^2}=\lim_{n\to\infty}\frac{1}{n}=0$

Hence:

$$n=o(n^2)$$

So $n^2$ is asymptotically larger.

---

Case 2: Limit Equals a Positive Constant

If:

$\lim_{n\to\infty}\frac{f(n)}{g(n)}=c,\quad 0<c<\infty$

then:

• Both functions grow at the same rate
• $f(n)=\Theta(g(n))$
  

---

Example

Compare:

$$f(n)=3n^2+2n$$

and

$$g(n)=n^2$$

Compute:

$\lim_{n\to\infty}\frac{3n^2+2n}{n^2}=\lim_{n\to\infty}\left(3+\frac{2}{n}\right)=3$

Since the limit is a positive constant:

$$f(n)=\Theta(n^2)$$

---

Case 3: Limit Equals Infinity

If:

$\lim_{n\to\infty}\frac{f(n)}{g(n)}=\infty$

then:

• $f(n)$grows faster than $g(n)$
  
• $f(n)=\omega(g(n))$

Example

Compare:

$$f(n)=n^3$$

and

$$g(n)=n^2$$

Compute:

${\lim }_{n\to \mathrm{\infty }}\frac{n^3}{n^2}=\infty$

Therefore:

$$n^3=\omega(n^2)$$

---

Common Growth Rates

The following ordering is fundamental in algorithm analysis:

$$1 < \log n < n < n\log n < n^2 < n^3 < 2^n < n!$$

---

Interpretation of Growth Rates

Function	Growth Type	Efficiency
$1$	Constant	Excellent
$\log n$	Logarithmic	Very Efficient
$n$	Linear	Efficient
$n\log n$	Linearithmic	Good
$n^2$	Quadratic	Moderate
$n^3$	Cubic	Slow
$2^n$	Exponential	Very Slow
$n!$	Factorial	Impractical

---

Dominant Term Principle

In asymptotic analysis, the highest-order term dominates.

---

Example 1

$$f(n)=5n^3+4n^2+7n+2$$

Dominant term:

$$n^3$$

Thus:

$$f(n)=\Theta(n^3)$$

---

Example 2

$$f(n)=1000n+50$$

Dominant term:

$$n$$

Thus:

$$f(n)=\Theta(n)$$

Ignoring Constants

Constant multipliers do not affect asymptotic growth.

---

Example

$$100n$$

and

$$n$$

have the same asymptotic size:

$$100n=\Theta(n)$$

because constants are ignored.

---

Comparing Polynomial Functions

For polynomials:

• Highest degree term determines growth.

---

Example

Compare:

$$n^2$$

and

$$n^5$$

Since degree 5 is larger:

$$n^2=o(n^5)$$

---

Comparing Logarithmic and Polynomial Functions

Any polynomial grows faster than logarithmic functions.

---

Example

$$\log n=o(n)$$

because:

$\lim_{n\to\infty}\frac{\log n}{n}=0$

---

Comparing Polynomial and Exponential Functions

Exponential functions grow faster than polynomial functions.

---

Example

$$n^5=o(2^n)$$

because:

$\lim_{n\to\infty}\frac{n^5}{2^n}=0$

---

Comparing Exponential and Factorial Functions

Factorial functions grow faster than exponentials.

---

Example

$$2^n=o(n!)$$

---

Summary Table for Comparing Function Sizes

Limit Result	Relationship
$0$	$f(n)=o(g(n))$
Positive constant	$f(n)=\Theta(g(n))$
$\infty$	$f(n)=\omega (g(n))$

---

Practical Importance in Algorithms

Comparing function sizes helps in:

• Choosing efficient algorithms
• Predicting scalability
• Understanding performance limits
• Designing optimized systems

---

Example in Sorting

Algorithm	Complexity
Bubble Sort	$O(n^2)$
Merge Sort	$O(n\log n)$

Since:

$$n\log n=o(n^2)$$

Merge Sort is asymptotically better.

---

Conclusion

Comparing the “sizes” of functions is central to asymptotic analysis. The comparison is based on how rapidly functions grow as input size increases.

The key tool is:

$\lim_{n\to\infty}\frac{f(n)}{g(n)}$

Using limits and asymptotic notations, we can classify functions into:

• Smaller growth
• Equal growth
• Faster growth

This enables rigorous comparison of algorithms independent of hardware and implementation details, forming the mathematical foundation of algorithm analysis.