9
$\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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\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)$.

Improve this answer
$\endgroup$
6
  • 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, 2012 at 19:54
  • 1
    $\begingroup$ The polynomial in this case is $n^{1-0.793} = n^{0.217}$. $\endgroup$
    – JeffE
    Sep 11, 2012 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, 2012 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, 2017 at 16:54
  • $\begingroup$ Isn't big Omega a lower bound on running time so that should say is "asymptotocially equal to or greater than" instead of " is polynomially larger than.." ? $\endgroup$
    – mLstudent33
    May 17, 2020 at 18:58
0
$\begingroup$

enter image description here

This is the solution. we have to compare with the general equation of master theorem

Improve this answer
$\endgroup$

Your Answer

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

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