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.