7
$\begingroup$

Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence

$$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$

by applying the Master Theorem.

I am very confused by how it is done. So, $a=3, b=4, f(n) = n\cdot \log(n)$
First step is to compare $n^{\log_b a} = n^{\log_4 3}= O(n^{0.793})$ with $f(n)$.

I have no clue on how they compared this. The book explains:

$f(n) = \Omega (n^{\log_4 3+\epsilon })$, where $\epsilon \approx 0.2$, case 3 applies if we can show that the regularity condition holds for $f(n).$

Followed by:

For sufficiently large n, we have that: $af\left(\frac{n}{b}\right) = 3\left(\frac{n}{4}\right)\log\left(\frac{n}{5}\right) \le\left(\frac{3}{4}\right)n \log n = cf(n)~ for~ c=\frac{3}{4}.$

Where did $3\left(\frac{n}{4}\right)$ come from?

$\endgroup$
10
$\begingroup$

If our recurrence takes the form $T(n) = aT(n/b) + f(n)$, then to use the "third case" of the Master method we must have the following hold:

$f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$ and if $a f(n/b) \leq c f(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$

Our recurrence is defined as $$T(n) = 3T(n/4) + n \log n.$$

By definition we have, $a = 3, b = 4, f(n) = n \log n$.

We now need to show that $f(n)$ is polynomially larger than $n^{\log_b a}$. That is the "$f(n) = \Omega(n^{\log_b a + \epsilon})$" part from above. Defining $\epsilon \approx 0.2$ achieves this. The reason being that $\log_4 3 \approx 0.793$ and $f(n) = \Omega(n^{0.793 + \epsilon})$.

We are left to show that $f(n)$ satisfies the regularity condition. That is the "$a f(n/b) \leq c f(n)$ for some constant $c < 1$ and all sufficiently large $n$" part.

We simply plug in our values of $a,b$ to get: $$a f(n/b) = 3(n/4) \log (n/4).$$ All we did was take the "$n$" in $f(n)$ and plug in "$n/4$".

To make this easier to see, let $k = n/4$ and observe that $a f(k) = a k \log k$. Swapping $k$ with $n/4$ we have $$3(n/4) \log (n/4) \leq (3/4)n \log n = c f(n)$$ where $c = 3/4$.

This finishes our necessary requirements and we have that $T(n) = \Theta(n \log n)$.

$\endgroup$
  • 1
    $\begingroup$ Thank you for detailed response. So, $n^{0.793}$ is polynomially $\leq$ than $ n^{1}\log n$ ? I probably misunderstood the meaning of "polynomially" $\endgroup$ – newprint Sep 11 '12 at 19:54
  • 1
    $\begingroup$ The polynomial in this case is $n^{1-0.793} = n^{0.217}$. $\endgroup$ – JeffE Sep 11 '12 at 22:00
  • $\begingroup$ @newprint Polynomially larger just means that the difference between the two is at least a (possibly fractional) power of $n$, not some smaller function, such as $(\log n)$. Specifically, it is exactly the condition for the "third case", that $f(n) = \Omega(n^{\log_b n} \cdot n^\epsilon)$. It is that extra $n^\epsilon$ factor that makes it polynomially larger. And as JeffE pointed out, in this case, $\epsilon = .217$. $\endgroup$ – Joe Sep 11 '12 at 22:29
  • $\begingroup$ Could we have chosen $\epsilon = 0.00000001$? As far as I understand $f(n)$ is already $\Omega(n^{0.793})$ so why do we need to add $0.2$? $\endgroup$ – Yos Apr 14 '17 at 16:54

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.