# Does T(n) = 2 · T(2n) + n apply to Master method?

I'm trying to apply the master method to the following recurrence:

$$T(n) = 2 \cdot T(2n)+n.$$

We have $$a=2$$ and $$b=1/2$$.

Also, $$f(n)=n$$ and $$n^{\log_b a} = n^{\log_{1/2} 2} = n^{-1}$$ since $$\log_{1/2} 2 = -1$$.

So, case 3 applies since $$f(n) = \Omega(n^{\log_b a+\epsilon })$$ , i.e., $$n = \Omega(n^{-1+2})$$ for some constant $$\epsilon = 2$$.

Now we have to check the regularity condition:

For some constant $$c<1$$, it must hold that $$af(n/b) \leq cf(n)$$.

That is (substitute $$a$$ and $$b$$ in the above regularity condition):

• $$2 \cdot 2n \leq c \cdot n$$
• $$4n \leq c \cdot n$$

Which cannot hold for any $$c < 1$$

Hence, we cannot apply case 3.

Is the above a correct application of Master theorem for this recurrence? And what would be the solution?

From wikipedia

"Here $$n$$ is the size of an input problem, $$a$$ is the number of subproblems in the recursion, and $$b$$ is the factor by which the subproblem size is reduced in each recursive call $$(b>1)$$"

So no. Master theorem can not be used to solve the given recurrence.

• Thanks for clarifying this important condition. So can we have an asymptotic bound on this recurrence? It seems no right? Dec 5, 2022 at 8:32
• Jarvis, just write down T(1) = c. Then write down other values of T(n) from your equation and try to find a pattern. For example T(2), T(4) etc. Dec 5, 2022 at 8:40
• You can reorganize the recurrence so that you have the "larger" (i.e. $T(2n)$) alone on the LHS, and then you get that $T$ indeed is $O(n)$. Dec 5, 2022 at 13:18
• Jarvis, are you just blindly plugging numbers into formulas? You need to actually understand what the given equation means. One look at the formula should make you think “hey, this looks strange…” Dec 6, 2022 at 9:14
• @RinkeshP: in fact, this problem is not about a feasible runtime, as the values of $T$ must be negative !
– user16034
Dec 6, 2022 at 12:43

The Master Theorem is not deemed to be used with $$b<1$$. But you can recast the recurrence as

$$T(2n)=\frac12T(n)-\frac n2$$

or

$$T(n)=\frac12T\left(\frac n2\right)-\frac n4.$$

So yes, the Master Theorem can be used.