comparison of two functions

Jul 23, 2025

Updated 1 day ago

2 min read

Growth Comparison of Functions Explained | Notehub

In algorithm analysis, growth comparison of functions is the foundation of understanding how efficiently an algorithm scales. Given two functions $t (n)$ and $g (n)$ , we want to know — as input size $n$ grows to infinity — which one grows faster, slower, or at the same rate?

This is essential mathematics for asymptotic notation (Big-O, Θ, Ω) and directly applies when comparing algorithms like merge sort vs quick sort.

Growth Comparison: The Limit Method

The standard tool for growth comparison of two functions is:

n \to \infty lim \frac{t ( n )}{g ( n )}

The result of this limit tells us the relationship between their orders of growth:

Result	Meaning
$= 0$	$t (n)$ has a smaller order of growth than $g (n)$
$= c$ (constant $> 0$ )	$t (n)$ has the same order of growth as $g (n)$
$= \infty$	$t (n)$ has a larger order of growth than $g (n)$

This limit-based growth comparison directly maps to asymptotic classes:

Result $0$ → $t (n) \in o (g (n))$ (little-o)
Result $c$ → $t (n) \in Θ (g (n))$
Result $\infty$ → $t (n) \in ω (g (n))$ (little-omega)

Worked Example: Growth Comparison of $n lo g_{2} n$ and $4^{n}$

Let:

$t (n) = n lo g_{2} n$
$g (n) = 4^{n}$

n \to \infty lim \frac{t ( n )}{g ( n )} = n \to \infty lim \frac{n lo g _{2} n}{4 ^{n}}

Direct substitution gives $\frac{\infty}{\infty}$ — an indeterminate form. We apply L'Hôpital's Rule.

Applying L'Hôpital's Rule

L'Hôpital's Rule states: if direct substitution yields $\frac{0}{0}$ or $\frac{\infty}{\infty}$ , differentiate numerator and denominator separately and re-evaluate the limit.

n \to \infty lim \frac{t ( n )}{g ( n )} = n \to \infty lim \frac{\frac{d}{d n} ( n lo g _{2} n )}{\frac{d}{d n} ( 4 ^{n} )}

Differentiating the Numerator

Using the product rule on $n lo g_{2} n$ :

\frac{d}{d n} (n lo g_{2} n) = n \cdot \frac{d}{d n} (lo g_{2} n) + lo g_{2} n \cdot \frac{d}{d n} (n)

Convert $lo g_{2} n$ to natural log:

lo g_{2} n = \frac{ln n}{ln 2} ⟹ \frac{d}{d n} lo g_{2} n = \frac{1}{ln 2} \cdot \frac{1}{n} = \frac{1}{n ln 2}

\frac{d}{d n} lo g_{2} n = \frac{1}{n ln 2}

So the numerator derivative:

n \cdot \frac{1}{n ln 2} + lo g_{2} n = \frac{1}{ln 2} + lo g_{2} n

Differentiating the Denominator

\frac{d}{d n} 4^{n} = 4^{n} ln 4

After First L'Hôpital

n \to \infty lim \frac{\frac{1}{ln 2} + lo g _{2} n}{4 ^{n} ln 4}

Still $\frac{\infty}{\infty}$ — apply L'Hôpital's Rule a second time.

Second Application of L'Hôpital's Rule

Differentiating the Numerator

\frac{d}{d n} (\frac{1}{ln 2} + lo g_{2} n) = 0 + \frac{1}{n ln 2} = \frac{1}{n ln 2}

Differentiating the Denominator

ln 4 \cdot \frac{d}{d n} (4^{n}) = ln 4 \cdot 4^{n} ln 4 = (ln 4)^{2} \cdot 4^{n}

Final Limit

n \to \infty lim \frac{\frac{1}{n ln 2}}{( ln 4 ) ^{2} \cdot 4 ^{n}} = n \to \infty lim \frac{1}{( n ln 2 ) ( ln 4 ) ^{2} \cdot 4 ^{n}}

As $n \to \infty$ , the denominator grows without bound while the numerator stays 1:

= \frac{1}{\infty} = 0

n \to \infty lim \frac{n lo g _{2} n}{4 ^{n}} = 0

Result and Interpretation

Since the limit $= 0$ :

t (n) = n lo g_{2} n has a smaller order of growth than g (n) = 4^{n}

In asymptotic terms: $n lo g_{2} n \in o (4^{n})$

This makes intuitive sense — exponential functions like $4^{n}$ always dominate polylogarithmic functions like $n lo g_{2} n$ as $n$ grows large. This is why exponential-time algorithms are considered infeasible for large inputs in algorithm design, while $O (n lo g n)$ algorithms like merge sort and quick sort are considered efficient.

Quick Reference: Common Growth Order (Slowest to Fastest)

Function	Name
$O (1)$	Constant
$O (lo g n)$	Logarithmic
$O (n)$	Linear
$O (n lo g n)$	Linearithmic
$O (n^{2})$	Quadratic
$O (2^{n})$	Exponential
$O (n!)$	Factorial

Each row dominates all rows above it in growth rate — exactly what the limit-based growth comparison method formally proves.

Related Notes:

Asymptotic Notation

Quick Sort

Merge Sort

Binary Search Recurrence

comparison of two functions

Growth Comparison of Functions Explained | Notehub

Growth Comparison: The Limit Method

Worked Example: Growth Comparison ofnlog2​n and4n

Applying L'Hôpital's Rule

Differentiating the Numerator

Differentiating the Denominator

After First L'Hôpital

Second Application of L'Hôpital's Rule

Differentiating the Numerator

Differentiating the Denominator

Final Limit

Result and Interpretation

Quick Reference: Common Growth Order (Slowest to Fastest)

Worked Example: Growth Comparison of $n lo g_{2} n$ and $4^{n}$