Solving T(n) = 3T(n/3)+n/2 using master method

Question

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?

Answer 1

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))$.

Answer 2

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.

Answer 3

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} )$

Answer 4

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)

Answer 5

This question can be solved by Master Theorem:
In a recursion form :

where a>=1, b>1, k >=0 and p is a real number, then:

1. if a > b^k, then
   

2. if a = b^k

      a.) if p >-1, then 
   

       b.) if p = -1, then 

       c.) if p < -1, then 

3. if a < b^k
a.) if p >=0, then

b.) if p<0, then T(n) = O(n^k)

So, the above equation

   T(n) = 3T(n/3) + n/3  

a = 3, b = 3, k =1, p =0    

so it fall into 2.a case, where a = b^k
So answer will be

O(n⋅log(n))