Results 1 to 2 of 2

Math Help - (Another) Algorithm Analysis

  1. #1
    Member
    Joined
    May 2009
    Posts
    109

    (Another) Algorithm Analysis

    Posted this orginally in my other thread but think I violated forum rules, so here it is.



    I really can't see what's going on here. How do you get to the third part from the second part? The way i see it you have 1/4 of n to play with but there seems to be n - 1?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    Posts
    461
    Hi.

    Quote Originally Posted by alyosha2 View Post
    Posted this orginally in my other thread but think I violated forum rules, so here it is.

    Yes, you are total violating the forum rules.

    Quote Originally Posted by alyosha2 View Post



    I really can't see what's going on here. How do you get to the third part from the second part? The way i see it you have 1/4 of n to play with but there seems to be n - 1?
    Well, CB gave you a perfect answer, I'm going to quote him (you can read it here : http://www.mathhelpforum.com/math-he...tml#post327278 )
    And you should give him "thanks" for his post, I already gave him reputation...

    It's a trivial application of the recurrence to itself:



    so:



    Now substitute this back into the first recurrence:



    CB
    I quote again and explain the last obvious step


    <br />
T(n) = 2T\left(\frac{n}{2}\right) + 2n - 1 (1)

    so:

    <br />
T(n/2) = 2T(n/4) + n - 1 (2)

    you see what happened here? Just substitute n := n/2 in (1)

    And now lets take a closer look to (1):

    <br />
 T(n) = 2T\left(\frac{n}{2}\right) + 2n - 1

    Do you see the T(n/2)? You know T(n/2), it is '(2)'
    Just use (2) in (1)

    <br />
 T(n) = 2*[2T(n/4) + n - 1  ]+ 2n - 1 ((2) in (1))

    You get it now?

    Yours
    Rapha
    Last edited by Rapha; June 9th 2009 at 02:48 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithm Analysis
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: July 1st 2009, 05:02 AM
  2. Algorithm analysis
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: June 4th 2009, 05:29 AM
  3. Algorithm Analysis - Big-oh, etc...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 8th 2009, 09:18 AM
  4. Algorithm analysis
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 17th 2009, 08:32 AM
  5. help me to prove this algorithm analysis
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: February 12th 2008, 08:13 PM

Search Tags


/mathhelpforum @mathhelpforum