Two Plus Two Older Archives  

Go Back   Two Plus Two Older Archives > Other Topics > Science, Math, and Philosophy
FAQ Community Calendar Today's Posts Search

Reply
 
Thread Tools Display Modes
  #1  
Old 09-07-2005, 06:53 PM
Aicirt Aicirt is offline
Junior Member
 
Join Date: Sep 2004
Posts: 3
Default need help finding bounds for recurrences

Im taking a graduate algorithms course without first taking an undergrad course. The prof assumes that we know a few concepts that I have not recieved and Im just a bit slow to pick up on some of these concepts. I was wondering if someone who has solved some recurrences in the past would be able to help me out with this. I understand how to solve them when I can apply the master theorm to the reccurence, but when it does not apply, I get stuck. Take for instance the following example:

T(n) = ( sqrt(n) ) * T(sqrt(n)) + n

Since the coefficient a, where T(n) = aT(n/b) + f(n), is not a constant, the master therom does not apply. I believe that there is some sort of transformation that I am supposed to do however Im not exactly sure how to do this. Also every single recurrence example in my text book uses constants for the a value. Anyone help get me started in the right direction?

Aicirt
Reply With Quote
Reply


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 12:31 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.