\documentclass[11pt]{article}
\include{lecture}


\begin{document}
\lecture{7}{08/01/2003}{Rela\c{c}\~{o}es de Recorr\^{e}ncia - M\'{e}todos de
An\'{a}lise}{Jociel C. Andrade e Mariella Berger}

%\draft % put this here only if you want to indicate this is a draft

\section{Mudan\c{c}a de Vari\'{a}veis}

\bigskip Algumas vezes \'{e} \'{u}til utilizar alguma forma de
manipula\c{c}\~{a}o alg\'{e}brica para transformar uma recorr\^{e}ncia em outra
similar que voc\^{e} j\'{a} tenha visto.\newline

\textbf{Exemplo:} Considere a recorr\^{e}ncia
\[T\left(n\right) = 2T(n^{\frac{1}{2}}) + \lg n.\]

Chame
\[m = \lg n\]

ent\~{a}o n\'{o}s temos:
\[
T(2^m) = 2T(2^{\frac{m}{2}}) + m
\]

Ajuste
\[S(m) = T(2^m)\]

portanto, n\'{o}s temos:
\[
S(m) = 2S(\frac{m}{2}) + m
\]

Esta recorr\^{e}ncia n\'os conhecemos e sabemos que
\[
S(m) = O(m\lg m)
\]

Mudando de volta de S(m) para T(n), n\'os obtemos:
\[
T(n) = T(2^m) = S(m) = O(m\lg m) = O(\lg n \lg\lg n)
\]

\newpage


\section{M\'{e}todo da Itera\c{c}\~{a}o}

Este m\'{e}todo consiste em expandir (iterar) a recorr\^{e}ncia e
express\'{a}-la como uma somat\'{o}ria de termos dependentes somente de n e das
condi\c{c}\~{o}es iniciais. A seguir n\'{o}s utilizamos t\'{e}cnicas para a
avalia\c{c}\~{a}o de somat\'{o}rias de modo a obter uma solu\c{c}\~{a}o de
f\'{o}rmula fechada para a recorr\^{e}ncia.

A chave do m\'{e}todo da itera\c{c}\~{a}o \'{e} focalizar-se sobre 2
par\^{a}metros:
\begin{itemize}
\item O n\'{u}mero de vezes que a recorr\^{e}ncia necessita ser iterada para
alcan\c{c}ar a condi\c{c}\~{a}o de fronteira;
\item A soma dos termos resultantes de cada n\'{i}vel do processo de
itera\c{c}\~{a}o.
\end{itemize}

\begin{example} Considere a recorr\^{e}ncia
\begin{equation}
T(n) = 3T(\frac{n}{4}) + n
\end{equation}

Expandindo esta recorr\^{e}ncia n\'{o}s obtemos
\begin{equation}
T(n) = n + 3(\frac{n}{4}) + 9T(\frac{n}{16}),
\end{equation}

expandindo mais uma vez
\begin{eqnarray}
T(n) &=& n + 3(\frac{n}{4}) + 9(\frac{n}{16}) + 27T(\frac{n}{64}), \nonumber  \\
T(n) &=& n + 3(\frac{n}{4}) + 9(\frac{n}{16}) + 27(\frac{n}{64}) + ... + 3^{\log_{4}n}T(1),\nonumber\\
T(n) &=& \sum_{i=0}^{(\log_{4}n)-1} n(\frac{3}{4})^i + 3^{\log_{4}n},\nonumber\\
T(n) &\leq& \sum_{i=0}^{\infty} n(\frac{3}{4})^i + n^{\log_{4}3},\nonumber\\
T(n) &\leq& 4n + n^{\log_{4}3}, \nonumber\\
T(n) &=& O(n)\nonumber.
\end{eqnarray}
\end{example}
\end{document}
