[Nizbel99]

Hey everyone, I'm having difficulties solving the recurrence relation:
T((n^2)/2^r) = n * T(n) + c*(n^2), for some constant c.

I've already solved a more specific case of the recurrence in an ealier problem:
T(n) = sqrt(n) * T(sqrt(n)) + n ; but I am having difficulties with this one because
of the 2^r part. I know that I'll end up having a subsitution m = n^2 then p = log(m)
(like I did the the specific one), then it's just a matter of proving the solution
(which I already know what it is) via induction.

However, I'm having trouble manipulation the general recurssion (with the 2^r) term.
Could someone help me re-write this recurrence in terms of T(n) or something similar?
I want to get rid of the 2^r term with some substituion perhaps, such that I get an expression
T(n) or T(m) = something, but I am not sure how.

I've attached an image of the original recurrence for clarity - Thank you

Zach

Attached File(s)

•  img.bmp (61.74K)
  Number of downloads: 132

This post has been edited by Nizbel99: 02 June 2010 - 08:47 AM

[RedSon]

The alternate form I found was:

n (c n+T(n)) = T(n^2 2^(-r))

And because I am lazy, I asked a computer to solve for c, I didn't check this so no warranty is explicit or implied...

n (c n+T(n)) = T(n^2 2^(-r))
Divide both sides by n:
c n+T(n) = (T(n^2 2^(-r)))/n
Subtract T(n) from both sides:
c n = (T(n^2 2^(-r))-n T(n))/n
Divide both sides by n:
c = (-n T(n)+T(2^(-r) n^2))/n^2

Let me know what you think

EDIT:
If it's garbage I can point the finger at Mathematica! Not me!!

This post has been edited by RedSon: 02 June 2010 - 08:58 AM

[Nizbel99]

RedSon, on 02 June 2010 - 07:57 AM, said:

The alternate form I found was:

n (c n+T(n)) = T(n^2 2^(-r))

And because I am lazy, I asked a computer to solve for c, I didn't check this so no warranty is explicit or implied...

n (c n+T(n)) = T(n^2 2^(-r))
Divide both sides by n:
c n+T(n) = (T(n^2 2^(-r)))/n
Subtract T(n) from both sides:
c n = (T(n^2 2^(-r))-n T(n))/n
Divide both sides by n:
c = (-n T(n)+T(2^(-r) n^2))/n^2

Let me know what you think

EDIT:
If it's garbage I can point the finger at Mathematica! Not me!!

That's not really what I meant by solve. The c is just an arbitrary constant. I basically have to show that T(n) = O(n*(log(n)^r) * n*log(log(n))) and I can prove this by induction. That's what I meant by "solving the recurrence". But in order for me to do that, I need an expression T(n) = something_goes_here, but instead, I have T((n^2)/2^r).

Say normally, if I had somthing like T(n) = 2T(n/2) + c, to solve the reccurence, I would show that T(n) = 2T(n/2) + c = 4*T(n/4) + 3c = 8T(n/8) + 7c = ... So after the i-th iteration, I would have T(n) = 2^i * T(n/(2^i)) + ((2^i) - 1)c, and setting 2^i = n, we would get that T(n) is in O(n) - Then I would prove my guess with induction. But for me to do that, I need.. T(n) = something_goes_here... which is my problem.

Hope I made things clearer - Thanks

Zach

This post has been edited by Nizbel99: 02 June 2010 - 10:09 AM

[Nizbel99]

John, on 05 June 2010 - 07:20 AM, said:

You can solve that recurrence using the same method as you did for a previous one.

Thanks =) - But I think the last term should be c*(a^2)*m =)

Zach