\documentstyle[11pt]{article} \advance\textwidth by1in\advance\oddsidemargin by-0.5in \advance\textheight by1.5in\topmargin 0pt\headheight 0pt \begin{document} \begin{center} \large\bf Some solved exercises about asymptotics \end{center} {\bf Exercise 2.6.} \begin{enumerate} \item Show that $3^n$ is not $O(2^n)$, but that $\log 3^n$ is $O(\log 2^n)$. If $3^n$ were $O(2^n)$, there would exist $c,N >0$ such that, for all $n> N$, $3^n \leq c\cdot 2^n$, or, equivalently, ${3^n\over c\cdot 2^n} \leq 1$. But, for any constant $c>0$, $$\lim_{n\rightarrow\infty} {3^n\over c\cdot 2^n} = c\cdot\lim_{n\rightarrow\infty}\bigl(\frac32\bigr)^n$$ diverges, so that no such $c$ and $N$ can exist. Assume that both logarithms are in base~2 (if they were in another base, we could convert both to base~2 by multiplying both by the same constant, which would not alter the relationship), Then $\log 3^n=n\log 3$ and $\log 2^n = n\log 2= n$; so we need to show that $n\log 3$ is $O(n)$. Pick $c=\log 3$; it is obvious that the inequality $n\log 3\leq c\cdot n$ holds for all $n>0$. \item Show that $n^n$ is not $O(n!)$, but that $\log n^n$ is $O(\log n!)$. $n!$ is difficult to manipulate. The easiest way to solve this problem is to use Stirling's approximation (bottom of page 80 in the text), which gives $n! = \Theta(\sqrt{n}(\frac{n}{e})^n)$. Using this, it is easy to prove both points. $n^n$ grows faster than $n!$, since the limit of their ratio, $$\lim_{n\rightarrow\infty} {n^n\over n!} = \lim_{n\rightarrow\infty} {n^n \over \sqrt{n}(\frac{n}{e})^n} = \lim_{n\rightarrow\infty} {e^n\over \sqrt{n}}$$ diverges. But $\log n^n=n\log n$, while $\log n! = \Theta(\frac12 n + n(\log n -\log e)) = \Theta(n\log n)$, so that the two functions grow at exactly the same rate. Without Stirling's approximation, we need more work. We begin by writing the inequality that would have to be respected if $n^n$ were $O(n!)$: for some $c$, $N$, we would have to have, for all $n>N$, $n^n\leq c\cdot n!$, or ${n^n \over n!}\leq c$. Consider the ratio: if we can show that it diverges, then no suitable constant $c$ can exist. Unfortunately, applying L'Hospital's rule right away would require differentiating $n!$---no easy task. So let us instead take logs on both sides of the inequality: $$n\log n - \sum_{i=1}^n \log i \leq \log c = c'$$ We can rewrite this inequality as $$\sum_{i=1}^n (\log n-\log i) \leq c'$$ The sum is not easy to manipulate, but note that the first $n/2$ terms are each at least as large as $\log n-\log(n/2)$, which is in turn just 1, so that we can write (for even $n$) $$\sum_{i=1}^n (\log n-\log i)\geq \sum_{i=1}^{n/2} (\log n -\log (n/2)) = \sum_{i=1}^{n/2} 1 = n/2$$ But that difference grows with $n$ and thus can never be bounded by a constant $c'$. For the logs, we can use ratios directly and use L'Hospital's rule to determine the convergence of these ratios. (Recall that the rule states that the limit of the ratio can be obtained by taking the limit of the ratio of the derivative of the numerator to the derivative of the denominator.)\ \ The limit of the ratio of the logarithms can be derived as follows. $$\lim_{n\rightarrow\infty} {\log n^n \over \log n!} = \lim_{n\rightarrow\infty} {n\log n\over \sum_{i=1}^n \log i}$$ Now apply L'Hospital's rule (the derivative of $\log n$ is $1/n$ times a constant, which drops out of the ratio---we could as easily have used logarithms in base $e$): $${}=\lim_{n\rightarrow\infty} {\log n\over \sum_{i=1}^n \frac{1}{i}}$$ Now note that the denominator, $\sum_{i=1}^n \frac{1}{i}$, is an approximation of the integral $\int_1^n \frac{1}{x}dx$; in fact, we can easily verify (visually, by looking at the rectangles given by the sum and at the curve $\frac{1}{x}$) that $$\int_1^{n+1}\frac{1}{x}dx < \sum_{i=1}^n {1\over i} < 1+ \int_1^n\frac{1}{x}dx$$ Since $\int_1^n\frac{1}{x}dx=\ln n$, it follows that $\sum_{i=1}^n\frac{1}{i}$ is $\Theta(\log n)$ and we are done. \item Show that, for $\alpha > 1$, $n^{\alpha\log n}$ is not $O(n^{\log n})$. but that $\log n^{\alpha\log n}$ is $O(\log n^{\log n})$. For $n^{\alpha\log n}$ to be $O(n^{\log n})$, we would have to find $c,N > 0$ such that, for all $n>N$, $n^{\alpha\log n}\leq c\cdot(n^{\log n})$. But the limit of the ratio ${n^{\alpha\log n}\over c\cdot(n^{\log n})}$ diverges, as we prove below: $$\lim_{n\rightarrow\infty} {n^{\alpha\log n}\over c\cdot(n^{\log n})} = \lim_{n\rightarrow\infty} {n^{\alpha\log n -\log n}\over c} = \lim_{n\rightarrow\infty} {n^{(\alpha-1)\log n}\over c}$$ Since $\alpha>1$, the numerator is $n$ raised to a power equal to some positive multiple of $\log n$ and thus grows as $n$ grows, whereas the denominator is a constant; therefore, the ratio diverges in the limit and no $c$ and $N$ can be found that meet the requirements. $\log n^{\alpha\log n} = \alpha\log n\log n = \alpha (\log n)^2$, while $\log n^{\log n} = \log n\log n = (\log n)^2$; thus the two are within a constant ratio ($\alpha$) of each other, so the result is clearly true. \end{enumerate} \medskip\noindent {\bf Exercise 2.8.} \begin{enumerate} \item Find functions $f_1$, $f_1$, $g_1$, $g_2$, such that $f_1$ is $\Omega(g_1)$, $f_2$ is $\Omega(g_2)$, and yet $f_1+f_2$ is not $\Omega(\max(g_1,g_2))$. We can find easy examples if we allow $f_2$ to assume negative values. For instance, define $f_1(n)=n$ and $f_2(n)=-n$; then $f_1(n)$ is $\Omega(n)$ and $f_2(n)$ is $\Omega(-n)$. But $f_1(n)+f_2(n)=0$ for all $n$ and thus is not $\Omega(n)$. If we restrict all functions to be positive, we need to use the notation ``upside-down,'' i.e., with simple functions $f_i$ and complicated functions $g_i$. For instance, let $g_1(n)$ be $n$ if $n$ is even, 1 otherwise and let $g_2(n)$ be $n$ if $n$ is odd, 1 otherwise; then $\max(g_1,g_2)(n)=n$. Now let $f_1(n)=f_2(n)=1$; we can easily verify that $f_i$ is $\Omega(g_i)$. Yet $(f_1+f_2)(n)=2$ is not $\Omega(n)$. \item Find functions $f_1$, $f_1$, $g_1$, $g_2$, such that $f_1$ is $\Omega(g_1)$, $f_2$ is $\Omega(g_2)$, and yet $f_1\cdot f_2$ is not $\Omega(g_1\cdot g_2)$, even if $g_i(n)>0$ for all~$n$. The simplest would be to use functions $f_i$ such that one equals zero whenever the other does not, with each equaling zero infinitely often. Since zero is not allowed, we can achieve the same effect with cancelling fractions. Let $f_1(n)$ be $n$ if $n$ is even, $\frac{1}{n}$ otherwise, and let $f_2(n)$ be $n$ if $n$ is odd, $\frac{1}{n}$ otherwise; then $(f_1\cdot f_2)(n)=1$ for all~$n$. Now we can trivially check that $f_i$ is $\Omega(n)$, yet $f_1\cdot f_2$, a constant 1, is not $\Omega(n^2)$. \end{enumerate} \end{document}