1. ## Algorithm question

this is kind of a follow on from my previous post.

$
T(n) = T(n - 1) + c + T(n - 1)
$

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

$
= 2(2T(n-2) + c) + c
$

$
= 2^{n}T(1) + c2^{n-1} + ... + c2 + c
$

$
= c2^{n} + c2^{n-1} + ... + c2 + c
$

= c(2^{n + 1} - 1)
$
= O(2^{n})
$

What I don't understand is how we get from the 3rd step to the 4th. If n is 5 then it will take 31 moves, which is what we have up to the 3rd step. Then the $2^{n}T(1)$ is 32 alone. What am i missing?

thanks.

2. Originally Posted by alyosha2
this is kind of a follow on from my previous post.

$
T(n) = T(n - 1) + c + T(n - 1)
$

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

$
= 2(2T(n-2) + c) + c
$

$
= 2^{n}T(1) + c2^{n-1} + ... + c2 + c
$

$
= c2^{n} + c2^{n-1} + ... + c2 + c
$

= c(2^{n + 1} - 1)
$
= O(2^{n})
$

What I don't understand is how we get from the 3rd step to the 4th. If n is 5 then it will take 31 moves, which is what we have up to the 3rd step. Then the $2^{n}T(1)$ is 32 alone. What am i missing?

thanks.
Note that $2(2T(n-2)+c)+c=2(2(2T(n-3)+c)+c)+c=2(2(2(2T(n-4)+c)+c)+c)+c=\dots$

You keep doing this until you get to $2(2(\dots2(2T(1)+c)+c)+\dotsc)+c)+c$

Now, multiply out to get:

$2^nT(1)+c2^{n-1}+\dots+c2^2+c2+c$

3. Originally Posted by alyosha2
this is kind of a follow on from my previous post.

$
T(n) = T(n - 1) + c + T(n - 1)
$

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

$
= 2(2T(n-2) + c) + c
$

$
= 2^{n}T(1) + c2^{n-1} + ... + c2 + c
$

$
= c2^{n} + c2^{n-1} + ... + c2 + c
$

= c(2^{n + 1} - 1)
$
= O(2^{n})
$

What I don't understand is how we get from the 3rd step to the 4th. If n is 5 then it will take 31 moves, which is what we have up to the 3rd step. Then the $2^{n}T(1)$ is 32 alone. What am i missing?

thanks.
You have:

$T_{n}=2T_{n-1}+c$

... $= 2(2T_{n-2}+c)+c=4T_{n-2}+2c+c$

... $= 4(2T_{n-3}+c)+2c+c=8T_{n-3}+4c+2c+c$

At each stage you get an the leading term becomes $2^{r}T_{n-r}+2^{r-1} c$ so:

$T_{n}=2^nT_{0}+c\sum_{r=0}^{n-1}2^r$

... $=2^nT_0+(2^n-1)c$

Hence:

$|T_{n}|=|2^nT_0+(2^n-1)c|\le |2^n(T_0+c)|+|c|$

and for $n$ large enough:

$|T_{n}|\le |2^n(T_0+c)|+2^n=2^n[|T_0+c|+1]$

So:

$T_n=O(2^n)$

CB

4. Originally Posted by Chris L T521
Note that $2(2T(n-2)+c)+c=2(2(2T(n-3)+c)+c)+c=2(2(2(2T(n-4)+c)+c)+c)+c=\dots$

You keep doing this until you get to $2(2(\dots2(2T(1)+c)+c)+\dotsc)+c)+c$

Now, multiply out to get:

$2^nT(1)+c2^{n-1}+\dots+c2^2+c2+c$
[assuming I have not got this dreadfully wrong}

Put $n=2$, then you have:

$T_2=2^2T_1+c2^1+c2^0=4T_1+2c+c$

But we know that:

$
T_2=2T_1+c
$

CB

5. Originally Posted by CaptainBlack
[assuming I have not got this dreadfully wrong}

Put $n=2$, then you have:

$T_2=2^2T_1+c2^1+c2^0=4T_1+2c+c$

But we know that:

$
T_2=2T_1+c
$

CB
I'm a bit confused. Are you saying that this part from the original post

$2^{n}T(1) + c2^{n -1} + ... + c2 + c$

is wrong also?

6. not sure i qute understand this part
$
T_{n}=2^nT_{0}+c\sum_{r=0}^{n-1}2^r
$

if c is part of the summation then if $n = 3$ then $c2^{0} + c2^{1} + c2^{2} = c6$ meaning i'm one move short. But the c is not part of the summation then there is no c in the summation. Am I missing something again?

Ignore this, just realised that raised to 0 is equal to 1.

7. Originally Posted by alyosha2
I'm a bit confused. Are you saying that this part from the original post

$2^{n}T(1) + c2^{n -1} + ... + c2 + c$

is wrong also?
It can be confusing doing the final stage, but ask what does this tell you about the value of $T_2$ ?

CB

8. Originally Posted by CaptainBlack
It can be confusing doing the final stage, but ask what does this tell you about the value of $T_2$ ?

CB
given that $T(1)$ is equal to $c$

$
2^{2}T(1) + c2^{1} + c = 7c
$

Which is wrong, but i don't know if i'm misunderstading the way it's supposed to be performed.

9. Originally Posted by alyosha2
given that $T(1)$ is equal to $c$

$
2^{2}T(1) + c2^{1} + c = 7c
$

Which is wrong, but i don't know if i'm misunderstading the way it's supposed to be performed.
Yes, it is wrong because you have miscounted the terms. I stopped with $T_0$ with the result you see above, if I wanted to stop at $T_1$ I would get:

$T_n=2^{n-1}T_1+c(2^{n-1}-1)=2^nc-c$

which satisfies the initial condition and the recurrence.

CB