Can I use Master Theorem if the partitions are not fractions?


by zeion
Tags: fractions, master, partitions, theorem
zeion
zeion is offline
#1
Mar2-12, 04:02 PM
P: 467
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(n-1) + f(n), what is b?
Phys.Org News Partner Science news on Phys.org
Lemurs match scent of a friend to sound of her voice
Repeated self-healing now possible in composite materials
'Heartbleed' fix may slow Web performance
Max.Planck
Max.Planck is offline
#2
Mar4-12, 01:40 PM
P: 127
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.
zeion
zeion is offline
#3
Mar5-12, 08:42 AM
P: 467
Quote Quote by Max.Planck View Post
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.
I'm not sure what a recursion tree method is..
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?

Max.Planck
Max.Planck is offline
#4
Mar5-12, 08:52 AM
P: 127

Can I use Master Theorem if the partitions are not fractions?


Quote Quote by zeion View Post

Actually nevermind, so if I find a closed form expression it will be 2^n, right?
Depends on C(0) and f(n). The recursion tree method should be described in your textbook.
zeion
zeion is offline
#5
Mar5-12, 09:42 AM
P: 467
Oh I see. It says that f(n) is constant. But it doesn't say what C(0) is.


Register to reply

Related Discussions
Statistics with Baye's theorem and partitions Precalculus Mathematics Homework 3
Asymptotic lower/upper bounds for T(n) [Master Theorem?] Calculus & Beyond Homework 0
Master Theorem Calculus & Beyond Homework 0