Results 1 to 3 of 3

Math Help - Recurrence relation

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    23

    Recurrence relation

    Hi, I try to solve this relation
    T(n) = 2n + 2nT(n/2), I try with substitutions but then i must calculate a sum that i find it difficult, so i wonder if there is an other way to go.
    Any ideas? Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by liberty View Post
    Hi, I try to solve this relation
    T(n) = 2n + 2nT(n/2), I try with substitutions but then i must calculate a sum that i find it difficult, so i wonder if there is an other way to go.
    Any ideas? Thanks in advance.

    Something seems to be lacking here: first, I pressume you know/you're given the few first elements T(0), T(1),..., and also: the given recurrence relation only works for even indexes: what happens with odd ones?

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    23
    Hi Tonio,correct.
    But we can skip this assuming that n is a power of 2. or we can solve this
    <br />
T(n) = 2n + 2nT(\left\lfloor {\frac{n}{2}} \right\rfloor )
    T(1) = 1.
    I would be glad with an approximate answer, for example like that O(n^{\log n} )
    Last edited by liberty; April 17th 2010 at 02:22 AM.
    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