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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 59, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9491005539894104, "perplexity": 419.3476607233226}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2016-44/segments/1476988719453.9/warc/CC-MAIN-20161020183839-00232-ip-10-171-6-4.ec2.internal.warc.gz"}