Results 1 to 9 of 9

Math Help - Algorithm question

  1. #1
    Member
    Joined
    May 2009
    Posts
    109

    Algorithm question

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

     <br />
T(n) = T(n - 1) + c + T(n - 1)<br />
    <br />
= 2T(n -1) + c<br />
    <br />
= 2(2T(n-2) + c) + c<br />
    <br />
= 2^{n}T(1) + c2^{n-1} + ... + c2 + c<br />
    <br />
= c2^{n} + c2^{n-1} + ... + c2 + c<br />
    = c(2^{n + 1} - 1)
    <br />
= O(2^{n})<br />

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Rhymes with Orange Chris L T521's Avatar
    Joined
    May 2008
    From
    Chicago, IL
    Posts
    2,844
    Thanks
    3
    Quote Originally Posted by alyosha2 View Post
    this is kind of a follow on from my previous post.

     <br />
T(n) = T(n - 1) + c + T(n - 1)<br />
    <br />
= 2T(n -1) + c<br />
    <br />
= 2(2T(n-2) + c) + c<br />
    <br />
= 2^{n}T(1) + c2^{n-1} + ... + c2 + c<br />
    <br />
= c2^{n} + c2^{n-1} + ... + c2 + c<br />
    = c(2^{n + 1} - 1)
    <br />
= O(2^{n})<br />

    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by alyosha2 View Post
    this is kind of a follow on from my previous post.

     <br />
T(n) = T(n - 1) + c + T(n - 1)<br />
    <br />
= 2T(n -1) + c<br />
    <br />
= 2(2T(n-2) + c) + c<br />
    <br />
= 2^{n}T(1) + c2^{n-1} + ... + c2 + c<br />
    <br />
= c2^{n} + c2^{n-1} + ... + c2 + c<br />
    = c(2^{n + 1} - 1)
    <br />
= O(2^{n})<br />

    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
    Last edited by CaptainBlack; August 4th 2009 at 06:34 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Chris L T521 View Post
    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:

     <br />
T_2=2T_1+c<br />

    CB
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2009
    Posts
    109
    Quote Originally Posted by CaptainBlack View Post
    [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:

     <br />
T_2=2T_1+c<br />

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2009
    Posts
    109
    not sure i qute understand this part
    <br />
T_{n}=2^nT_{0}+c\sum_{r=0}^{n-1}2^r<br />
    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.
    Last edited by alyosha2; August 5th 2009 at 03:00 AM. Reason: sorry just realised that raised to 0 is equal to 1.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by alyosha2 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2009
    Posts
    109
    Quote Originally Posted by CaptainBlack View Post
    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

     <br />
2^{2}T(1) + c2^{1} + c = 7c<br />

    Which is wrong, but i don't know if i'm misunderstading the way it's supposed to be performed.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by alyosha2 View Post
    given that T(1) is equal to c

     <br />
2^{2}T(1) + c2^{1} + c = 7c<br />

    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
    Last edited by CaptainBlack; August 5th 2009 at 05:40 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simple question on EM algorithm
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: February 25th 2011, 07:10 PM
  2. [SOLVED] algorithm Question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 6th 2010, 11:30 AM
  3. Simple log question for algorithm
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: May 28th 2009, 02:15 PM
  4. Question on algorithm (Sorting)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 26th 2009, 08:35 AM
  5. Algorithm Question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 4th 2007, 03:29 AM

Search Tags


/mathhelpforum @mathhelpforum