Results 1 to 2 of 2

Math Help - Asymptotic Analysis of Recursive Powering

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    US
    Posts
    1

    Asymptotic Analysis of Recursive Powering

    I am currently going through MITs course on Algorithms online for my own knowledge. One particular problem I'm having trouble with is doing asymptotic analysis on the recursive powering algorithm provided on the following page: MIT's Introduction to Algorithms, Lecture 3: Divide and Conquer - good coders code, great reuse. I've tried to write the recurrence equation for this and have:

    T(n) = a when n = 1
    T(n) = T(n/2) + b when n is even
    T(n) = T(n-1/2) + c when n is odd

    where a, b and c are all constants. I've labeled them differently just so I can keep track that while they are all constants, they are each different. For example a is the constant of returning a value, b is a constant for summing two values and c is for summing three values. I'm a bit stuck here and would like to ensure that my recurrence equation is correct and then see the steps that one would take to clearly show that T(n) = O(lg(n)). Any examples would be greatly appreciated. Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17

    Re: Asymptotic Analysis of Recursive Powering

    I think you mean that T(n) = T((n-1)/2) + c when n is odd.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Language recursive, sat recursive
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 25th 2012, 11:29 AM
  2. Asymptotic
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 30th 2011, 01:02 AM
  3. Asymptotic analysis
    Posted in the Calculus Forum
    Replies: 5
    Last Post: March 17th 2009, 04:36 PM
  4. Asymptotic analysis
    Posted in the Calculus Forum
    Replies: 0
    Last Post: March 17th 2009, 12:33 PM
  5. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 29th 2009, 08:32 AM

Search Tags


/mathhelpforum @mathhelpforum