
\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial9}{Problem Solutions for Tutorial 9}{April 14, 1997}

\begin{problems}

\problem

{ \em
Find a $\Theta(\cdot)$ bound for
\[
T(n) = T(\sqrt{n}) + \lg \lg n.
\]
The base condition is $T(2)=1$.
}

\[ T(n) = T(\sqrt{n}) + \lg \lg n \]
Substitute $n=2^m$ and note that $m=\lg n$.

\[ T(2^m) = T(2^{\frac{m}{2}}) + \lg m \]

Let $S(m) = T(2^m)$, noting that the base case is $S(m=1) = T(2)$ so 

\begin{eqnarray*}
T(n) = T(2^m) = S(m) &=& S(\frac{m}{2}) + \lg m  \\
&=& S(\frac{m}{2}) + \lg m \\
&=& \lg m + \lg(m/2) + \lg(m/4) \cdots \lg(2) + S(1) \\
&=& \sum_{i=0}^{(\lg m)-1}( \lg \frac{m}{2^i}) + S(1) \\
&=& \sum_{i=0}^{(\lg m)-1}( \lg m - i) + S(1) \\
&=& (\lg m - 1) ( \lg m) - \sum_{i=0}^{(\lg m)-1} i + 1 \\
&=& (\lg m - 1) ( \lg m) - \frac{(\lg m - 1) (\lg m )}{2} + 1 \\
&=& \frac{(\lg m - 1) (\lg m)}{2} + 1 \\
&=& \frac{(\lg \lg n - 1) (\lg \lg n)}{2} + 1 \\
\end{eqnarray*}

So, $T(n)$ is $\Theta ((lg \lg n)^2)$.




\problem 

{\em
Consider the linear recurrence \\
$T(n) = \sum_{i=1}^d a_{i}T(n/2^i) + G(n)$
}

\begin{itemize}
{ \em 
\item Find a transformation $n \rightarrow m$ that will convert this problem io a difference equation of the form \\
$f(m) = \sum_{i=1}^d a_{i}f(m-i) + g(m)$ \\

}
Let $n=2^m$ and $f(m) = T(2^m)$.

{\em 
\item Apply your results to find the solution of the recurrence relation \\
$T(n) = 2T(n/2) + 3T(n/4) + nlogn$
}

Find the homogeneous solution first:

Guess a solution of $f(m) = c x^m$.  $cx^m = 2c x^{m-1} + 3 c x^{m-2}$.
$x^2 - 2 x^1 - 3 x = 0$.  And the solutions are $x=-3,1$.

So the solution is $T(2^m) = f(m) = C_1 (-3)^m + C_2$.

And the overall solution is 
$T(n) = T(2^m) = C_1 (-3)^{\lg n} + C_2 + D n \log n$.

\end{itemize}


\problem 

{ \em
Compute the following limits.

}

\begin {itemize}
\item $\sum_{i=1}^{\infty} \frac {1}{i(i+1)}$.

Using partial fractions, we find that 
$\frac {1}{i(i+1)} = \frac {1}{i} - \frac {1}{i+1}$.

\[ \sum_{i=1}^{\infty} (\frac {1}{i} - \frac {1}{i+1}) =
  (1 - \frac {1}{2}) + (\frac {1}{2} - \frac {1}{3}) +
  (\frac {1}{3} - \frac {1}{4}) + (\frac {1}{4} - \frac {1}{5}) + \ldots \]

\[ = 1 - \lim_{n \rightarrow \infty} \frac{1}{n} =1 \]

This series is known as a telescoping summation since pairs of terms cancel.

\item $ \lim_{n \rightarrow \infty}  1/n + 1/(n+1) + \ldots + 1/2n$

$ 1/n + 1/(n+1) + \ldots + 1/2n) \leq \int_{n-1}^{2n} \frac{1}{n} dn = \left. \ln n \right|_{n-1}^{2n} = \ln (\frac{2n}{n-1})$

$ 1/n + 1/(n+1) + \ldots + 1/2n) \geq \int_{n}^{2n+1} \frac{1}{n} dn = \left. \ln n \right|_{n}^{2n+1} = \ln (\frac{2n+1}{n}) $


$ \lim_{n \rightarrow \infty} \ln (\frac{2n+1}{n}) = 2$
$ \lim_{n \rightarrow \infty} \ln (\frac{2n}{n-1}) = 2$

So the sum has a tight bound of 2.


% \item $ \lim_{n \rightarrow \infty} \frac{n}{2^n} \sum_{k=1}^{n}\frac{2^k}{k}$


\end{itemize}



\end{problems}

\end{document}

