3-3

Ordering by asymptotic growth rates
a.Rank the following functions by order of growth; that is, find an arrangement g1, g2, .....g30 of the functions satisfying $g1 = \Omega(g2)$, $g2 = \Omega(g3)$ . . . ,$g29 = \Omega(g30)$. Partition your list into equivalence classes such that functions f(n) and g(n) are in the same class if and only if $f(n) = \theta(g(n))$.

$\lg\lg(n)$ $2^{\lg^*n}$ ${(\sqrt2)}^{\lg(n)}$ $n^2$ $n!$ $(\lg(n))!$
$(\frac{3}{2})^n$ $n^3$ $\lg^2(n)$ $\lg(n!)$ $2^{2^{n}}$ $n^{ \frac{1}{\lg(n)}}$
$\ln{\ln(n)}$ $\lg^*n$ $n . 2^n$ $n^{\lg{\lg(n)}}$ $ln(n)$ 1
$2^{\lg(n)}$ $(\lg n)^{\lg n}$ $e^n$ $4^{lg n}$ $(n+1)!$ $\sqrt {lg n}$
$\lg^*(\lg n)$ $2 ^ \sqrt{2 lg n}$ $n$ $2^n$ $n \lg n$ $2 ^{2^{n+1}}$

b.Give an example of a single nonnegative function f .n/ such that for all functions g(n) in part (a), f(n) is neither $O(g_i(n))$ nor $\Omega(g_i(n))$.
Solution:
a. If functions are on same they realted by $\theta$ else thoose higher will be $\Omega$ functions below The solution will easier if it is calculated from bottom to top. $$2^{2^{n+1}}$$ $$2^{2^{n}}$$ $$(n + 1)!$$ $$n!$$ see equation 14 $$en$$ see equation 12 $$ n · 2^n $$ $$2^n$$ $$(3/2)^n$$ $$(\lg n)^{\lg n} = n ^ {\lg \lg n}$$ see equation11 $$(\lg n)! $$ see equation 10 $$n3$$ $$n^2 = 4^{\lg n}$$ see equation 9 $$n \lg n and \lg(n!)$$ see equation 8 $$n = 2^{lg n}$$ see equation 7 $$(\sqrt 2) ^ {lg n} = \sqrt n $$ see equation 6 and 15 $$2 ^ {\sqrt{2 lgn}} $$ see equation 4 $$\lg^2 n$$ $$\ln n$$ $$\sqrt \lg n$$ $$\ln \ln n $$ see equation 3 $$ 2 ^ {\lg^∗ n} $$ $$ \lg^∗ n and \lg^∗(lg n)$$ see equation 2 $$ \lg(\lg^∗)n$$ $$n ^ {1/ lg n}(= 2) and 1 $$ see equation 1
Below rules are useful in ranking
 • Exponential functions grow faster than polynomial functions, which grow faster than polylogarithmic functions.
• The base of a logarithm doesn’t matter asymptotically, but the base of an exponential and the degree of a polynomial do matter.
b. The following f (n) is nonnegative, and for all functions $g_i (n)$ in part (a), f(n) is neither $O(g_i (n))$ nor $ \Omega(gi (n))$.
f (n) = $2^{2^{n+2}}$ if n is even ,
0 if n is odd . The above function will be greater than $2^{2^{n+1}}$ if n is even and 0 if n is odd.
1 is a constant $$2^{\lg(n)} = n $$ since logarithm base is 2 and it is raised to power 2 raising both sides to $\frac{1}{\lg n}$ $$ \begin{equation} 2 = n^{\frac{1}{\lg n}} \end{equation}$$ since this is equal to 2 which is also a constant $$2 = n^{\frac{1}{\lg n}} = \theta(1) $$ The iterated logarithm is slow growing function if you see the definition of iterated algorithm the value is very for no of atoms in the universe.If you apply a log on iterated logarithm it will be even lower. $$\lg (\lg^{*}n)$$ From iterated algorithm definition $$\lg^{*}n = \lg^{*}{\lg n}+1$$ we can easily prove this as the definition suggests iterated algorithm is no of times the logarithm must be so the result is <= 1. By induction we can prove above equation. ex: $$\lg^{*}2 = 1$$ $$\lg^{*}2 = 1 + \lg^{*}{\lg 2} $$ $$\lg^{*}2 = 1 + \lg^{*}{1} $$ since $\lg^{*}{1}$ is zero bcoz we dont have to apply iterated logarithm since result is already 1 $$\lg^{*}2 = 1 $$ $$\lg^{*}{\lg n} = \lg^{*}n-1$$ hence $$\begin{equation}\lg^{*}{\lg n} = \theta(\lg^{*}n)\end{equation}$$ $$\begin{equation}\ln \ln n = \omega(2 ^ {lg ^{∗} n})\end{equation}$$ $$\begin{equation}2^{\sqrt{2 lg n}} = \omega(lg^2 n) \end{equation}$$ Proof for equation 4 we have prove below equation result is infinity (according to definition which means numerator is upper bound for large value of n hence we need to prove result is infinity ) $$ \lim_{n\to\infty} \frac{2^{\sqrt{2 lg n}}} {lg^2 n}$$ When an equation is in indeterminate form we can apply derivative to convert to determinate form (derivative is rate of change of function) Applying derivative (involves chain rule becoz of complex functions) derivative of $2^{\sqrt{2 lg n}}$ is $\frac{2^{\sqrt{2 lg n} } . ln 2}{n. \sqrt{2 lg n}}$ (tip: see derivative of 2^x applying lg on sides) applying derivative for 3 times we finally get $$ \lim_{n\to\infty} \frac{ \ 2^{\sqrt{2 lg n} } {ln 2}^3} {3}$$ The above equation will be infinity when n tends to infinity.
Applying log on both sides of eq 4 $$ \sqrt{2 lg n} = 2 lg lg n $$ $$\begin{equation} \sqrt{2 lg n} = \omega(2 lg lg n) \end{equation} $$ $$\begin{equation} (\sqrt{2}) ^ {lg n} = \sqrt{n} \end{equation} $$ see log basics $$\begin{equation} 2 ^ {lg n} = n \end{equation} $$ $$\begin{equation} \lg (n!) = (n lg n) \end{equation} $$ Through Stirling's approximation 3.16 eq in the book $$\begin{equation} n^2 = 4 ^{lg n} \end{equation} $$ $$\begin{equation} (\lg n)! = \omega( n ^ 3) \end{equation} $$ proof for equation 9 applying logarithm for numerator and denominator $$ \lim_{n\to\infty} \frac{ (\lg \lg n)! } { 3 lg n } $$ applying Stirling approximation $$ \lim_{n\to\infty} \frac{ lg n . lg lg n } { 3 lg n } $$ $$ \lim_{n\to\infty} \frac{ lg lg n } { 3 } $$ The above equation will be infinity when n tends to infinity $$\begin{equation} (\lg n)^{\lg n} = n ^ {\lg lg n} \end{equation} $$ $$\begin{equation} e^{n} = \omega(n . 2^n) \end{equation} $$ proof for equation 12 $$ \lim_{n\to\infty} \frac {2^n (\frac{e}{2})^{n} } {n . 2^n} $$ $$ \lim_{n\to\infty} \frac {(\frac{e}{2})^{n} } {n } $$ Applying derivative to above eq $$ \lim_{n\to\infty} \frac {n (\frac{e}{2})^{n-1} } {n } $$ $$\lim_{n\to\infty} (\frac{e}{2})^{n-1} $$ the above equation will be infinity when n tends to infinity $$ \begin{equation} n! = \theta(n^{n+\frac{1}{2}} e^{−n}) \end{equation} $$ The above equation is obtained through Stirling's approximation by ignoring constants and lower order terms $$\begin{equation} n! = \omega{e^n} \end{equation} $$ proof for equation 14: $$\lim_{n\to\infty} \frac {n!} {e^n} $$ substitute from eq 13 for $n!$ $$\lim_{n\to\infty} \frac {n^{n+\frac{1}{2}} e^{−n}} {e^n} $$ $$\lim_{n\to\infty} \frac {n^{n+\frac{1}{2}}} {e^{2n}} $$ applying natural logarithm for numerator and denominator $$\lim_{n\to\infty} \frac {\ln {n^{n+\frac{1}{2}}}} {\ln e^{2n}} $$ $$\lim_{n\to\infty} \frac { {n+\frac{1}{2}} \ln {n}} {2n} $$ applying derivative for above eq $$\lim_{n\to\infty} \frac { {n+\frac{1}{2}} \ln {n}} {2n} $$ $$\lim_{n\to\infty} \frac { \ln {n} + \frac {1}{n} ({n+\frac{1}{2}}) } {2} $$ $$\lim_{n\to\infty} \frac { n \ln {n} + ({n+\frac{1}{2}}) } {2n} $$ applying derivative for above eq again $$\lim_{n\to\infty} \frac { \ln {n}+ n . \frac {1}{n} + 1 } {2} $$ $$\lim_{n\to\infty} \frac { \ln {n}+ 2} {2} $$ The above equation will be infinity when n tends to infinity $$\begin{equation} (\sqrt 2) ^{ lg n} = \omega( 2 ^{\sqrt{2 \lg n}}) \end{equation} $$