3
$\begingroup$

I thought I understood the Master Method quite well till I saw this question

$T(n) = 3T(\frac{n}{3})+\frac{n}{2}$

My approach: $a = 3 ; b=3$ and $f(n) = \frac{n}{2}$

$n^{\log_b{a}}$ = $n^{log_3{3}} = n$

This looked like a classic solution of master method using case 1.

But since case 1 implies $f(n) = n^{\log_3{3} - ε}$ and I cannot find any way that ε can be represented, I understand that case 1 is not the way.

However the solution says that this is solvable by case 2 of the master method and the solution is $T(n) = \theta(n^{log_3{3}} \log^{ n}) $

Case 2 of the master method states that if $f(n) = n^{log_b{a}} \log^{k}{ n}$ then $T(n) = \theta(n^{log_b{a}} \log^{k+1}{ n}) $

Can someone explain how this is solved using case 2 of the master method and why this fits under case 2?

$\endgroup$
  • $\begingroup$ Where did the $+e$ come from? What's $e$? I think you'll need to provide more context. Please edit the question to show your work and where you got that expression. Also, why do you think case 1 is appropriate? Please spell out your reasoning. Give us something to work with; the more you can share your thinking, the more likely we can help you. $\endgroup$ – D.W. Sep 4 '16 at 15:12
  • $\begingroup$ @D.W. e stands for episilon. case 1 of the master method states that if $f(n) is O(n^{\log_b{a -ε}})$ where $a>0,b>1$ then $T(n) is \theta (n^{\log_b{a}})$.. Updated the question to reflect the -ε instead of +ε $\endgroup$ – WizCrack Sep 4 '16 at 15:43
  • $\begingroup$ Note that you don't calculate the running time of the recurrence, whatever that would be. You attempt to solve the recurrence. $\endgroup$ – Raphael Sep 4 '16 at 21:00
  • 1
    $\begingroup$ Our reference question explains the Master theorem at length. Duplicate? $\endgroup$ – Raphael Sep 4 '16 at 21:02
0
$\begingroup$

In a recurrence of the form:

$$T(n)=aT(n/b)+O(n^d)$$

Case 2 of the master theorem applies when we do equal work at every level of the recursion tree. This happens when the amount of work done at the root - $O(n^d)$ - is equal to the amount of work done at the leaves. In other words, when the rate of subproblem proliferation (RSP) is equal to the rate of work shrinkage (RWS) per subproblem:

  • The RSP is $a=3$ in your recurrence. This means that, as we move down the tree, we have more subproblems to solve (which is bad news). In particular, at level $j$, we have $3^j$ subproblems.

  • The RWS is $b^d=3^1=3$ in your recurrence. This means that, as we move down the tree, each subproblem does less and less work (which is good news). In particular, at level $j$, each subproblem accounts for $O(n/3^j)$ of the total amount of work.

Since $a=b^d$, the RSP and the RWS cancel out. Thus, it is easy to predict what the running time will be. Since we have a logarithmic number of levels - $log(n)$ - and the total amount of work is the same at every level - $O(n)$ - then the running time is $O(n \cdot log(n))$.

$\endgroup$
  • 1
    $\begingroup$ @ Mario Cervera. Thanks. It makes perfect sense. I ran this through a recursion tree. At each level, the total work done was n/2. Therefore the total work done by the entire tree is the sum of work done at each level. i.e. $(n/2 + n/2 +. . .+n/2) \log{n}$ times. $\endgroup$ – WizCrack Sep 4 '16 at 17:39
1
$\begingroup$

While applying master's theorem all you have to do is compare which of $f(n)$ or $(n^{\log_b{a}})$ is asymptotically greater. The greater of the two functions determines the solution to the recurrence. There are only possible outcomes for this comparison:
[1] $(n^{\log_b{a}})$ is asymptotically greater than $f(n)$
[2] Both are asymptotically equal
[3] $f(n)$ is asymptotically greater than $(n^{\log_b{a}})$

Yours falls in case 2.

$\endgroup$
0
$\begingroup$

Case 2 of masters theorem says that:

if f(n) = θ(n^(logb a)), then T(n) = θ(n^(logb a)logn).

^ means power.

In term log n of θ(n^(logb a)logn), the base does not matter.

So going by your way, you are right in saying that

a = 3; b = 3 and f(n) = n^2

f(n) = n/2

f(n) <= 2*(n/2) for all n > 1, this means that:

f(n) = O(n)

Also

f(n) >= 0.8*(n/2) for all n > 1, this means that:

f(n) = omega(n)

Hence f(n) = θ(n)

Therefore, the solution is T(n) = θ(nlogn)

$\endgroup$
0
$\begingroup$

In the recurrence relation $T(n)=3T(\frac{n}{3})+\frac{n}{2}$

The last term $\frac{n}{2}$ can be written as $n\cdot\frac{1}{2}$ aka $n\cdot c$ cause $\frac{1}{2}$ is a constant.

From Masters Theorem:

$n^{\log_{3}(3)} =1$. So, $n^1= f(n)$

This resembles case 2 of masters theorem $T(n) = \theta(n^{\log_{b}{a}}\log_{2}{n} )$

thus, $T(n) = \theta(n\log_{}{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.