Master Theorem Question $T (n) = 3/2T (2n/3)+ n$

Question

I was solving Master Theorem examples, I came across following example

$(3/2)T(2n/3)+n$

I am confused about what will be value of $ a=3/2$?

What will be proposed recurrence solution?

Answer 1

Given, recurrence relation is:

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

Standard master recurrence relation is:

$$T(n) = a T\left(\frac{n}{b}\right) + n$$

Your given recurrence relation can be written as:

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

So, $a = 3/2$ and $b = 3/2$. Now apply Master Theorem Case $(2)$:

$$T(n) = \Theta(n.\log n)$$

Answer 2

One of the cases of the Master's theorem says that if $T(n) = aT(n/b) + f(n)$ and $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$. In your example, $a=b=3/2$, and so $\log_b a = 1$. The condition $f(n) = \Theta(n^{\log_b a})$ is satisfied because $n = \Theta(n^1)$, and so the solution to the recurrence is $T(n) = \Theta(n^1 \log n) = \Theta(n \log n)$.