# Math Help - (Another) Algorithm Analysis

1. ## (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?

2. Hi.

Originally Posted by alyosha2
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.

Originally Posted by alyosha2

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

$
T(n) = 2T\left(\frac{n}{2}\right) + 2n - 1$
(1)

so:

$
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):

$
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)

$
T(n) = 2*[2T(n/4) + n - 1 ]+ 2n - 1$
((2) in (1))

You get it now?

Yours
Rapha