Pesquisa(n)

Caso Base:

$$\begin{eqnarray*} T\left( 1\right) & = & 1\\ T\left( n\right) & = & 1+\left( n-... ...t( \frac{3}{5}n\right) \\ & = & n+T\left( \frac{3}{5}n\right) \end{eqnarray*}$$

Aplicando o Master Theorem[1, p62], tendo que , e , chegamos ao resultado que

$$T\left( n\right) =\Theta \left( f\left( n\right) \right) =\Theta \left( n\right)$$

de qualquer forma, pelo método da substituição:

$$T\left( n\right) = n+T\left( \frac{3}{5}n\right)$$ (1)

$$T\left( \frac{3}{5}n\right) = \frac{3}{5}n+T\left( \frac{3^{2}}{5^{2}}n\right)$$ (2)

$$T\left( \frac{3^{2}}{5^{2}}n\right) = \frac{3}{5}n+T\left( \frac{3^{3}}{5^{3}}n\right)$$ (3)

$$\vdots$$ (4)

$$T\left( \left( \frac{3}{5}\right) ^{i}n\right) = \left( \frac{3}{5}\right) ^{i}n+T\left( \left( \frac{3}{5}\right) ^{i+1}n\right)$$ (5)

$$\vdots$$ (6)

$$T\left( \left( \frac{3}{5}\right) ^{k}n\right) = 1$$ (7)

Ora, chegaremos ao fim da recursão quando

$$\left( \frac{3}{5}\right) ^{k}n = 1$$ (8)

$$k\log _{\frac{3}{5}}n = 1$$ (9)

$$k = \log _{\frac{5}{3}}n$$ (10)

Logo,

$$T\left( n\right) = \left( \frac{3}{5}\right) ^{0}n+\left( \frac{3}{5}\right) ^{1}n+\ldots +\left( \frac{3}{5}\right) ^{k}n$$ (11)

$$= \sum ^{k}_{i=0}\left( \frac{3}{5}\right) ^{i}n$$ (12)

$$= \sum _{i=0}^{\log _{\frac{3}{5}}n}\left( \frac{3}{5}\right) ^{i}n$$ (13)

$$= n\frac{1-\frac{3}{5}^{1+\log _{\frac{5}{3}}n}}{1-\frac{3}{5}}$$ (14)