Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Solving Recurrence Equations

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    16

    Solving Recurrence Equations

    I am trying to solve this Recurrence Equation and convert it into big O notation using substitution T(n) = T(n/2) + c
    So...
    I calculated:

    Code:
    T(n) = T(n/4) + 2c
    T(n) = T(n/8) + 3c
    T(n) = T(n/2^k) + kc
    Now I'm lost. Some resources talk of setting n - k = 0 but I don't see how this can help and why you can do this?
    Last edited by Ifailatmaths; April 19th 2012 at 05:11 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Solving Recurrence Equations

    You should have some initial condition T(1) = b for some constant b. Then T(2^k) = b + kc. If n = 2^k, then k = log(n) (logarithm to the base 2). Therefore, T(n) = b + c*log(n) = O(log(n)).

    When n is not a power of 2, then the solution depends on whether / is regular division or integer division (which throws away the remainder). In the first case, you need more initial conditions to define T(n) for all n; in fact, you need to know T(n) for all odd natural numbers n. In the second case, I think you can prove that T(n) is monotonic (not necessarily strictly) and you can still have the O(log(n)) bound.
    Thanks from Ifailatmaths
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving a recurrence relation.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 11th 2011, 02:05 PM
  2. Solving recurrence systems
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: May 15th 2010, 06:05 AM
  3. Need help solving recurrence formula
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 7th 2009, 12:08 PM
  4. Solving Recurrence Relation
    Posted in the Calculus Forum
    Replies: 0
    Last Post: February 16th 2009, 04:43 PM
  5. Solving a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 12th 2009, 10:19 PM

Search Tags


/mathhelpforum @mathhelpforum