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

• $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?

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.

StackExchange Computer Science Q#155936, answer score: 13