Results 1 to 5 of 5

Math Help - I need help solving a recurrence

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    22

    I need help solving a recurrence

    assuming that n is a power of 2 T(n) = (2 + \frac{1}{\log{n}})T(n/2) for n >= 2 with T(1)= 1

    Its for an algorithms course and the answer needs to be in asymptotic notation.

    I tried repeated substitution but things are getting complicated pretty fast. It does produce some pattern but it is not jumping out at me. Does anyone have some advice on an alternative?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member MaxJasper's Avatar
    Joined
    Aug 2012
    From
    Canada
    Posts
    482
    Thanks
    55

    Lightbulb Re: I need help solving a recurrence

    Quote Originally Posted by restin84 View Post
    assuming that n is a power of 2 T(n) = (2 + \frac{1}{\log{n}})T(n/2) for n >= 2 with T(1)= 1Its for an algorithms course and the answer needs to be in asymptotic notation. I tried repeated substitution but things are getting complicated pretty fast. It does produce some pattern but it is not jumping out at me. Does anyone have some advice on an alternative?
    Check this out:

    T\left[2^k\right]=\prod _{i=1}^k \left(2+\frac{1}{\text{Ln}\left[2^i\right]}\right) :::: T[1] = 1,.... k\geq 1
    Last edited by MaxJasper; September 23rd 2012 at 07:27 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Re: I need help solving a recurrence

    Quote Originally Posted by MaxJasper View Post
    Check this out:

    T\left[2^n\right]=\prod _{i=1}^n \left(2+\frac{1}{\text{Ln}\left[2^i\right]}\right) :::: T[1] = 1,.... n\geq 2
    So I guess that since I'm seeing T[n^2] I should be using a change of variable?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member MaxJasper's Avatar
    Joined
    Aug 2012
    From
    Canada
    Posts
    482
    Thanks
    55

    Lightbulb Re: I need help solving a recurrence

    Quote Originally Posted by restin84 View Post
    So I guess that since I'm seeing T[n^2] I should be using a change of variable?
    You said n is a power of 2 : n=2,4,8,... \to 2^k,k=1,2,3,\text{...}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: I need help solving a recurrence

    Let P(k) = (2 + 1/1)(2 + 1/2) ... (2 + 1/k) and P(0) = 1. Then T(2^k) = P(k). It is clear that P(k)\le 3^k=(2^k)^{\log3}, so T(n)\le n^{\log3}\le n^{1.6}. It is possible to show by induction that P(k)\le2^k\cdot k, so T(n)\le n\log n, which is a much better upper bound.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving Recurrence Equations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 20th 2012, 05:42 AM
  2. Solving a recurrence relation.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 11th 2011, 03:05 PM
  3. Solving recurrence systems
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: May 15th 2010, 07:05 AM
  4. Need help solving recurrence formula
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 7th 2009, 01:08 PM
  5. Solving a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 12th 2009, 11:19 PM

Search Tags


/mathhelpforum @mathhelpforum