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

Question

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?

Answer 1

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.

Answer 2

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.