Results 1 to 5 of 5

Math Help - big o recurrence relation

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    9

    big o recurrence relation

    I have a simple recurrence relation describing algorithm complexity:
    T(1) = 1
    T(N) = 2 * T(N/2) + 1

    What I attempted:
    let k = log2(N)
    T(N) = 2^K * T(N/(2^K)) + K
    = 2^(log2(N)) * T(1) + k
    = N + log2(N)

    However I know that the complexity is 2N-1. Can someone point out where I am going wrong?
    Edit:
    I realized that
    T(N) = 2^K * T(N/(2^K)) + K should be T(N) = 2^K * T(N/(2^K)) + N
    which yields a final solution of 2N. I'm still losing the -1 constant and would like to know why.

    Furthermore, if I have a relation
    T(1) = 1
    T(N) = 4 * T(N/2) + 1

    Any suggestions how to approach this one?
    Last edited by Bicubic; March 31st 2011 at 01:22 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    I realized that
    T(N) = 2^K * T(N/(2^K)) + K should be T(N) = 2^K * T(N/(2^K)) + N
    It should be T(N) = 2^K * T(N/(2^K)) + 2^(K-1) + 2^(K-2) + ... + 1 = 2^K * T(N/(2^K)) + 2^K - 1. When 2^K = N, this means T(N) = N * T(1) + N - 1 = 2N - 1.

    Furthermore, if I have a relation
    T(1) = 1
    T(N) = 4 * T(N/2) + 1

    Any suggestions how to approach this one?
    Approach it in the same way: expand the equation several times. I get T(N) = 4^K * T(N/(2^K)) + 4^(K-1) + 4^(K-2) + ... + 1 = (2^K)^2 * T(N/(2^K)) + ((2^K)^2 - 1) / 3.

    If you need a big-O estimate, see the Master theorem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2010
    Posts
    9
    Thank you very much! I missed the fact that the constant is multiplied by the number of recurring calls at each level.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2010
    Posts
    9
    Hi, I just had some time to work on the second recurrence with
    T(N) = 4 * T(N/2) + 1

    Everything works out except for the constant term. I describe it as the sum 4^0+4^1+..+4^N-1 and am not sure how to reduce it to a single function. The case 2^N was trivial. Is there any general solution to these?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    I wrote it above: it's (4^N - 1) / 3. It's the sum of a geometric progression.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 15th 2011, 11:27 PM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 02:15 AM
  3. Recurrence Relation HELP
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2009, 01:18 PM
  4. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 06:20 PM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 08:02 AM

Search Tags


/mathhelpforum @mathhelpforum