$\displaystyle

T(n) = T(n-1) + c + T(n - 1) = 2T(n - 1) + C = 2(2(T(n - 2) + c) + c)

$

It's the towers of hanoi algorithm in case that helps.

Printable View

- Aug 3rd 2009, 06:20 AMalyosha2Is this wrong?
$\displaystyle

T(n) = T(n-1) + c + T(n - 1) = 2T(n - 1) + C = 2(2(T(n - 2) + c) + c)

$

It's the towers of hanoi algorithm in case that helps. - Aug 3rd 2009, 07:02 AMSoroban
Hello, alyosha2!

Quote:

$\displaystyle T(n) \:= \:T(n-1) + c + T(n - 1) \;=\; 2T(n - 1) + c \;=\; 2\bigg[2(T(n - 2) + c\bigg] + c$

It's the "Towers of Hanoi" algorithm in case that helps.

Consider the first few values of the sequence.

. . $\displaystyle n$ = number of disks, $\displaystyle T(n)$ = number of moves.

. . $\displaystyle \begin{array}{|c|c|}

n & T(n) \\ \hline

1 & 1 \\

2 & 3 \\

3 & 7 \\

4 & 15 \\

5 & 31 \\

\vdots & \vdots \end{array}$

The recursive form is: .$\displaystyle T(n) \;=\;2\!\cdot\!T(n-1) + 1$

. . The closed form is: .$\displaystyle T(n) \;=\;2^n - 1$

- Aug 4th 2009, 04:21 AMalyosha2
- Aug 4th 2009, 04:49 AMCaptainBlack
- Aug 4th 2009, 04:58 AMalyosha2
- Aug 4th 2009, 05:47 AMCaptainBlack