DAA Assignment 1

Created

Jul 29, 2025

Last Modified

3 months ago

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

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

$\frac{\infty}{\infty}$ This is an $\frac{\infty}{\infty}$ form, so apply L'Hopital's Rule

t^{'} (n) = \frac{d}{d n} \cdot n^{2} = 2 n

$g^{'} (n) = \frac{d}{d n} (n \cdot lo g_{2} n)$ $\frac{\infty}{\infty}$ $= lo g_{2} n \frac{d}{d n} n + n \frac{d}{d n} lo g_{2} n$ $= lo g_{2} n + n \cdot \frac{1}{n ln 2}$ $g^{'} (n) = lo g_{2} n + \frac{1}{ln 2}$	$\frac{d}{d n} lo g_{2} n = \frac{d}{d n} \frac{ln n}{ln 2}$ $= \frac{1}{ln 2} \cdot \frac{d}{d n} ln n$ $3^{n}$ $n^{2}$ $2^{n d}$ $n lo g_{2} n$ $\frac{d}{d n} lo g_{2} n = \frac{1}{n ln 2}$

\frac{t ^{'} ( n )}{g ^{'} ( n )} = \frac{2 n}{lo g _{2} n + \frac{1}{l n 2}}

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

t = a + b

t (n) = \frac{d}{d n} \cdot 2 n

t (n) = 2

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

g " (n) = \frac{d}{d n} lo g_{2} n + 0

g " (n) = \frac{1}{n ln 2}

\frac{t " ( n )}{g " ( n )} = \frac{2}{( 1/ n ln 2 )}

\frac{t " ( n )}{g " ( n )} = 2 \cdot n ln 2

n \to \infty lim = \infty

\infty implies t(n) has larger order of growth than g(n)

t (n) > g (n)

n^{2} > n lo g_{2} n

let
t(n) = $n^{2}$
g(n) = $3^{n}$

n \to \infty lim \frac{t ( n )}{g ( n )} = n \to \infty lim \frac{n ^{2}}{3 ^{n}}

This is an $\frac{\infty}{\infty}$ form, so apply L'Hopital's Rule

t^{'} (n) = \frac{d}{d n} \cdot n^{2} = 2 n

g^{'} (n) = \frac{d}{d n} \cdot 3^{n}

g^{'} (n) = 3^{n} ln 3

\frac{t ^{'} ( n )}{g ^{'} ( n )} = \frac{2 n}{3 ^{n} ln 3}

n \to \infty lim \frac{2 n}{3 ^{n} ln 3} = \frac{\infty}{\infty}

t " (n) = \frac{d}{d n} \cdot 2 n = 2

g " (n) = \frac{d}{d n} 3^{n} ln 3

g " (n) = ln 3 \frac{d}{d n} \cdot 3^{n}

g " (n) = ln 3 \cdot 3^{n} \cdot ln 3

g " (n) = (ln 3)^{2} \cdot 3^{n}

\frac{t " ( n )}{g " ( n )} = \frac{2}{( ln 3 ) ^{2} \cdot 3 ^{n}}

n \to \infty lim = \frac{2}{\infty}

n \to \infty lim = 0

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

t (n) < g (n)

n^{2} < 3^{n}