1
$\begingroup$

I am having difficulties in understanding why the recurrence

$$T(n)=3T(n/4) + n\log n$$

is solvable with Master Method but

$$T(n)=2T(n/2) + n\log n$$

isn't?

Despite they both look very similar except the values of coefficient '$a$' and size cutter '$b$'.

I understand that the work function '$f(n)$' must be polynomially larger/smaller than $n^{\log_ba}$. And that in second recurrence $n^{\log_22}=n$ is not polynomially comparable to $f(n)=n\log n$. So Master Method cannot be applied. But why can it be applied to the first recurrence?

I found these examples in CLRS Intro to Algo book, and can't understand them. Can you please explain.

$\endgroup$
1
$\begingroup$

Let us use the master theorem as stated on Wikipedia. Consider a recurrence $$ T(n) = aT(n/b) + f(n). $$ There are several cases to consider:

  1. If $f(n) = O(n^c)$ for $c < \log_b a$ then $T(n) = \Theta(n^{\log_b a})$.
  2. If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k \geq 0$ then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.
  3. If $f(n) = \Omega(n^c)$ for $c > \log_b a$ and $f(n)$ is "reasonable" then $T(n) = \Theta(f(n))$.

In the third case, a function is "reasonable" if there exist $k < 1$ and $N$ such that for $N \geq n$, we have $af(n/b) \leq kf(n)$.

There are also extensions of the second case that handle all values of $k$:

  1. If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k > - 1$ then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.
  2. If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k = - 1$ then $T(n) = \Theta(n^{\log_b a} \log\log n)$.
  3. If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k < - 1$ then $T(n) = \Theta(n^{\log_b a})$.

Now back to your recurrences. The values of $a,b$ and $f(n)$ are:

  1. $a=3$, $b=4$, $f(n) = n\log n$.
  2. $a=2$, $b=2$, $f(n) = n\log n$.

In the first recurrence, $f(n) = \Omega(n^1)$, where $1 > \log_4 3$, and so, according to the third case of the master theorem, $f(n) = \Theta(n\log n)$ (you have to check that the function $n\log n$ is reasonable).

In the second recurrence, $f(n) = \Theta(n^1 \log^1 n)$, where $1 = \log_2 2$, and so, according to the second case of the master theorem, $f(n) = \Theta(n\log^2 n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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