Can I use Master Theorem if the partitions are not fractions?
1. The problem statement, all variables and given/known data
If I had a recurrence expression that recurs on partitions of size n  1 each time, (as opposed some fraction of the original size ie. n/2), how can I apply the Master Theorem? I don't know what the "b" value is? 2. Relevant equations 3. The attempt at a solution ie. If I had 2 C(n1) + f(n), what is b? 
Re: Can I use Master Theorem if the partitions are not fractions?
You can not use the Master Theorem in this case, just use the recursion tree method. In this case it is easy to see that it will be exponential, since each level has twice the number of nodes of the previous level.

Re: Can I use Master Theorem if the partitions are not fractions?
Quote:
I see that each recursion will have twice the calls to the function as the last, but they are also on one less element than the last, does that matter? Actually nevermind, so if I find a closed form expression it will be 2^n, right? 
Re: Can I use Master Theorem if the partitions are not fractions?
Quote:

Re: Can I use Master Theorem if the partitions are not fractions?
Oh I see. It says that f(n) is constant. But it doesn't say what C(0) is.

All times are GMT 5. The time now is 06:26 AM. 
Powered by vBulletin Copyright ©2000  2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums