Solve recurrence relation using Master's method -> T(n) = 2T(n/2) + n^2 when n is even and T(n) = 2T(n/2) + n^3 when n is odd

1
votes

T(n) ={ 2T(n/2) + n^2 when n is even and T(n) = 2T(n/2) + n^3 when n is odd

I solved this separately and i am getting the solution as theta(n^2) if n is even and theta(n^3) if n is odd from case 3 of master's theorem. But i am not supposed to solve this problem separately.

How to solve a recurrence relation like this together?

T(n) ={ 2T(n/2) + n^2 when n is even and T(n) = 2T(n/2) + n^3 when n is odd

Is it solvable by master's theorem or master's theorem does not apply?

Kindly help me with this.

1
algorithmtime-complexityrecurrencemaster-theorem
combine them into one relation. you will get something like n^3 + (n-1)^2 as the cost of the current step. What you see then? - kelalaka
Hint: look at the bit pattern of n. - meowgoesthedog
you should say = T(n) ={ 2T(**floor**(n/2)) + n^2 when n is even and T(n) = 2T(n/2) + n^3 when n is odd, or something else. - kelalaka
@kelalaka you meant floor to be in the odd part, probably. - Yola
@Yola. Your solution is not complete. because on odd at the end will make it cubic? - kelalaka

1 Answers

1
votes

Suppose n = 2^k for some integer k, so n equals to 100...00. Then you can apply master method the even part of the recurrence. and obtain theta(n^2).

Now suppose there is also 1 not in the most significant bit, e.g. 100100..00. So, you will have at least one level in your recursion-tree all nodes of which add up to n^3 * constant, and by this you obtain theta(n^3).

Thus, the answer is theta(n^2) if n is a power of two and theta(n^3) otherwise. But if we first encounter odd n and it is equal to a base case then it might not be cubic.

After some chatting with kelalaka it came to me that if first 1 is k-th from the right in n then if k > (2/3)(1/lg 2)lg n, we don't care any more about (n/2^k)^3. It is still O(n^2).