4
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thanks for clarifying this important condition. So can we have an asymptotic bound on this recurrence? It seems no right? $\endgroup$
    – Jarvis
    Dec 5, 2022 at 8:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – gnasher729
    Dec 5, 2022 at 8:40
  • 3
    $\begingroup$ 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)$. $\endgroup$
    – Pål GD
    Dec 5, 2022 at 13:18
  • 2
    $\begingroup$ 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…” $\endgroup$
    – gnasher729
    Dec 6, 2022 at 9:14
  • 2
    $\begingroup$ @RinkeshP: in fact, this problem is not about a feasible runtime, as the values of $T$ must be negative ! $\endgroup$
    – user16034
    Dec 6, 2022 at 12:43
13
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.