[Solved]: Solving T(n) = 3T(n/3)+n/2 using master method

Problem Detail: 

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?

Asked By : WizCrack

Answered By : Mario Cervera

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63133

3.2K people like this

 Download Related Notes/Documents