comparison of two functions

Created

Jul 23, 2025

Last Modified

3 months ago

Compare the growth of two functions

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

0 implies $t (n)$ has smaller order of growth than $g (n)$
c implies $t (n)$ has same order of growth as $g (n)$
$\infty$ implies $t (n)$ has larger order of growth than $g (n)$

Compare the growth of the function $n lo g_{2} n$ and $4^{n}$

let
t(n) = $n l o g_{2} n$
g(n) = $4^{n}$

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

\frac{\infty lo g _{2} \infty}{4 ^{\infty}} = \frac{\infty}{\infty}

This is an $\frac{\infty}{\infty}$ form, so apply L'Hopital’s Rule (differentiate numerator and denominator):

Apply L hopital Rule

According to L Hopital can only be applied in the case where direct substitution yields an indeterminate form, meaning $\frac{0}{0}$ or $\frac{\infty}{\infty}$ .

n \to \infty lim \frac{\frac{d}{d n} ( n l o g _{2} n )}{\frac{d}{d n} 4 ^{n}}

\frac{d}{d n} (n l o g_{2} n)

\frac{n \frac{d}{d n} ( l o g _{2} n ) + \frac{d}{d n} ( n ) \cdot l o g _{2} n}{\frac{d}{d n} ( 4 ^{n} )}

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

$lo g_{2} n = \frac{l n n}{l n 2}$

\frac{d}{d n} \frac{ln n}{ln 2}

\frac{1}{ln 2} \cdot \frac{d}{d n} lo g 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}

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

Put the value

\frac{n \cdot \frac{1}{n l n 2} + 1 \cdot l o g _{2} n}{4 ^{n} ln 4}

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

Again, apply L hopital Rule

Differentiate numerator

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

0 + \frac{1}{n ln 2} = \frac{1}{n ln 2}

Differentiate denominator

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

ln 4 \cdot 4^{n} ln 4

(ln 4)^{2} \cdot 4^{n}

Put the values:

\frac{1 / n ln 2}{( ln 4 ) ^{2} \cdot 4 ^{n}}

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

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

0 implies t(n) has smaller order of growth than g(n)

t (n) = n lo g_{2} n

g (n) = 4^{n}