I have the following recursion: T(n) = 2*T(n/4) + T(n/2) + n and I need to know the exact equation, I know Master theorem won't help me, and the iteration seems to be wrong...
Please tell me how to do it in general for such recursions. Thanks in advance.
Hey all, thanks for replying I need complexity. I need to understand how to solve such problems.
T(n) = O(nlogn) and W(nlogn)
To prove that, by definition of O, we need to find constants n0 and c such that:
for every n>=n0, T(n)<=cnlogn.
We will use induction on n to prove that T(n)<=cnlogn for all n>=n0
Let's skip the base case for now... (we'll return later)
Hipothesis: We assume that for every k<n, T(k)<=cklogk
Thesis: We want to prove that T(n)<=cnlogn
But, T(n)=2T(n/4)+T(n/2)+n
Using the hipothesis we get:
T(n)<=2(c(n/4)log(n/4))+c(n/2)log(n/2)+n=cnlogn + n(1-3c/2)
So, taking c>=2/3 would prove our thesis, because then T(n)<=cnlogn
Now we need to prove the base case:
We will take n0=2 because if we take n0=1, the logn would be 0 and that wouldn't work with our thesis. So our base cases would be n=2,3,4. We need the following propositions to be true:
T(2) <= 2clog2
T(3) <= 3clog3
T(4) <= 4clog4
So, by taking c=max{2/3, T(2)/2, T(3)/3log3, T(4)/8} and n0=2, we would be finding constants c and n0 such that for every natural n>=n0, T(n)<=cnlogn
The demonstration for T(n) = W(nlogn) is analog.
So basically, in these cases where you can't use the Masther Theorem, you need to 'guess' the result and prove it by induction.
For more information on these kind of demonstrations, refer to 'Introduction to Algorithms'
First of all you need to define some limits on this, otherwise it won't ever end and you will stuck up with OverflowException. Something like the n is integer and the minimal value is 0.
Could you please bring up more details on your question in this manner ?
This won't help you figure out how to do it necessarily, but apparently Wolfram Alpha can get the right answer. Perhaps you can look for documentation or have Mathematica show you the steps it takes in solving this:
Wolfram Alpha: T(n)=2*T(n/4)+T(n/2)+n
To put crude upper and lower bounds on the search space, you could have recognized your T(n) is bounded above by 3T(n/2) + n and below by 2T(n/4) + n... so O(n^(3/2)) and W(n), by the master theorem.
In general, solving recurrence relations hard problem.
