3-2

Relative asymptotic growths Indicate, for each pair of expressions (A,B) in the table below, whether A is $O$, $o$, $\Omega$,$\omega$ or $\theta$ of B. Assume that $k \geq 1$,$\epsilon$ > 0, and c > 1 are constants. Your answer should be in the form of the table with “yes” or “no” written in each box.

A	B	$O$	$o$	$\Omega$	$\omega$	$\theta$
$lg^k{n}$	$n^\epsilon$	Yes	Yes	No	No	No
$n^k$	$c^n$	Yes	Yes	No	No	No
$\sqrt{n}$	$n^{\sin {n}}$	No	No	No	No	No
$2^n$	$2^{n/2}$	No	No	Yes	Yes	No
$n^{lgc}$	$c^{lgn}$	Yes	No	Yes	No	Yes
$lg{(n!)}$	$lg{(n^n)}$	Yes	No	Yes	No	Yes

a. If $f(n) = o(n)$ then by definition $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ Since A is to expressed in the form B(see the question A as $O,0\theta $ etc). A is f(n) and B is g(n) $$\lim_{n \to \infty} \frac{\lg^k{n}}{n^\epsilon}$$ The above equation is in indeterminate form. lets apply L'Hôpital's Rule which will convert this in to determinate form.Applying differential to numerator and denominator. $$\lim_{n \to \infty} \frac{k (lg^{k-1}{n})}{ \epsilon (n^\epsilon-1) n^1}$$ $$\lim_{n \to \infty} \frac{k (lg^{k-1}{n})}{ \epsilon (n^\epsilon)}$$ IF we apply L'Hôpital's Rule k times for numerator and denominator $$\lim_{n \to \infty} \frac{k (k-1) (k-2)...1}{ \epsilon^k (n^\epsilon)}$$ As you can see the numerator is a constant value for real big values of n (n approaches infinity) the equation is true. hence $f(n) = o(g(n))$ and it is not $f(n) = \omega(g(n))$ Lets try to prove $f(n) = O(n)$ from defination $$0 \leq f(n) \leq c g(n) $$ $$0 \leq \lg^k{n} \leq c n^\epsilon $$ $$0 \leq \frac{\lg^k{n}} {n^\epsilon} \leq c $$ by L'Hôpital's Rule the fractional part goes to zero hence $f(n) = O(n)$ for $f(n) = \theta(g(n))$ it should be bounded by upper and lower bound since it is true for only. $f(n) is not \theta(g(n))$
 b. If $n^k = o(c^k)$ then $$\lim_{n \to \infty} \frac{n^k}{c^n}$$ lets apply L'Hôpital's Rule which will convert this in to determinate form.Applying differential to numerator and denominator. $$\lim_{n \to \infty} \frac{k n^{k-1}}{n c^{n-1}}$$ IF we apply L'Hôpital's Rule k times for numerator and denominator $$\lim_{n \to \infty} \frac{k (k-1)... 1 }{n^k c^{n-k}}$$ As you can see the numerator is a constant value for real big values of n (n approaches infinity) the equation is true. hence $f(n) = o(g(n))$ and it is not $f(n) = \omega(g(n))$
 c. $\sqrt{n}$ and $n^{\sin {n}}$ since sin graph varies between 1 and -1 $n^{\sin {n}}$ never settles for a smaller or bigger value. $\sqrt{n}$ is either greater than $n^{\sin {n}}$ or less than $n^{\sin {n}}$. Hence we cannot any of the relations.
 d. $2^n$ and $2^{n/2}$ $$\lim_{n \to \infty} \frac{2^n }{2^{n/2}}$$ $$\lim_{n \to \infty} 2^{n/2} $$ this equation approaches when n approaches infinity. hence $2^n = \omega{2^{n/2}}$ lets verify f(n) = $\Omega(g(n))$ $$0 \leq 2^n \leq c 2^{n/2}$$ $$0 \leq 2^{n/2} \leq c $$
 e. $n^{lgc}$ and $c^{lgn}$ both the equation are same. we can write $n^{lgc}$ as $c^{lg_c{n^{lgc}}} $ $$c^{lg_c{n}(lgc)} $$ $$c^{\frac{lgn(lgc)}{lgc}} $$ $$c^{lgn} $$ since both the equations are same all the equality relations are true i.e $O$ , $\theta$ , $\Omega$
 f. $lg{(n!)}$ and $lg{(n^n)}$
by Stirling's approximation $lg{(n!)}$ = $\theta(n lgn)$ which means both the equations are same hence all equality relations are true again.