How to apply Master theorem to this relation?

Question

This is the definition of master theorem I am using(from Master Theorem)

I am trying to use that master theorem to find the tight bound for this relation
$T(n) = 9T(\frac{n}{3}) + n^3*log_2(n)$

What value of c would I use for the theorem here based on that definition? 3 or 4?

Answer 1

By way of enrichment we solve another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and $T(1)=T(2)=1$ and for $n\ge 3$

$$T(n) = 9 T(\lfloor n/3 \rfloor) + Q n^3 \lfloor \log_3 n \rfloor.$$

The constant $Q$ is to indicate the conversion from $\log_2 n$ to $\log_3 n.$

Furthermore let the base three representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 3^k.$$

Then we can unroll the recurrence to obtain the following exact formula for $n\ge 3$ $$T(n) = 9^{\lfloor \log_3 n \rfloor} + Q\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 9^j (\lfloor \log_3 n \rfloor-j) \left( \sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^{k-j} \right)^3 \\ = 9^{\lfloor \log_3 n \rfloor} + Q\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 3^{-j} (\lfloor \log_3 n \rfloor-j) \left( \sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^k\right)^3.$$

Now to get an upper bound consider a string of two digits which yields $$T(n) \le 9^{\lfloor \log_3 n \rfloor} + Q \sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 3^{-j} (\lfloor \log_3 n \rfloor-j) \left( 2 \times \sum_{k=j}^{\lfloor \log_3 n \rfloor} 3^k\right)^3 \\ = 9^{\lfloor \log_3 n \rfloor} + Q \sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 3^{-j} (\lfloor \log_3 n \rfloor-j) \left( 3^{\lfloor \log_3 n \rfloor+1} - 3^j\right)^3.$$

This simplifies to $$3^{2\lfloor \log_3 n \rfloor} + Q\left(\frac{81}{2}\lfloor \log_3 n \rfloor-\frac{81}{4}\right) 3^{3\lfloor \log_3 n \rfloor} \\ +Q\left(\frac{1719}{64}-\frac{27}{2}\lfloor \log_3 n \rfloor^2 -\frac{27}{2}\lfloor \log_3 n \rfloor\right) 3^{2\lfloor \log_3 n \rfloor} \\ -Q\left(\frac{9}{2}\lfloor \log_3 n \rfloor + \frac{27}{4}\right) 3^{\lfloor \log_3 n \rfloor} + Q\frac{1}{8} \lfloor \log_3 n \rfloor + Q\frac{9}{64}.$$

Note that this bound is attained and cannot be improved.

The lower bound is for the case of a one digit followed by a string of zeros and yields $$T(n) \ge 9^{\lfloor \log_3 n \rfloor} + Q \sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 3^{-j} (\lfloor \log_3 n \rfloor-j) \left( 3^{\lfloor \log_3 n \rfloor}\right)^3 \\ = 9^{\lfloor \log_3 n \rfloor} + Q 3^{3\lfloor \log_3 n \rfloor} \sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 3^{-j} (\lfloor \log_3 n \rfloor-j).$$

This simplifies to $$3^{2\lfloor \log_3 n \rfloor} + Q\left(\frac{3}{2} \lfloor \log_3 n \rfloor - \frac{3}{4}\right) 3^{3\lfloor \log_3 n \rfloor} + Q\frac{3}{4} 3^{2\lfloor \log_3 n \rfloor}.$$

The lower bound too is attained.

We can observe the distinction between the recursive component and the base case component quite clearly here. Moreover since $9=3^2$ we get a lower order term which is quadratic in $n.$

Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$\color{#0A0}{\lfloor \log_3 n \rfloor 3^{3\lfloor \log_3 n \rfloor}} \in \Theta\left(\log_3 n \times 3^{3 \log_3 n}\right) = \Theta\left(\log n \times n^3\right).$$

Note that Akra-Bazzi applies and the reader is invited to do this calculation.

Answer 2

You can only give upper and lower bounds. For a lower bound use $n^3 \log_2 n = \mathcal o(n^3)$ and for the upper bound $n^3 \log_2 n = \mathcal O(n^{3+\epsilon})$ for any $\epsilon > 0$.

Now since $\log_3 9 = 2 < 3 < 3+\epsilon$, you fall into case 1. thus $$T(n) = \mathcal O(n^{3+\epsilon}) \wedge T(n) = \mathcal o(n^3)$$

I suspect you could show that $T(n) = \Theta(n^3\log n)$, but I'm not going to go deeper on that.

Answer 3

What I did to solve this problem in the end is using this twist of the Master Theorem(from Master Theorem)

So if we evaluate this relation $T(n) = 9T(\frac{n}{3}) + n^3*log_2(n)$
With this definition, $a$ = 9, $b$ = 3, $f(n) = n^3*log_2(n)$.
So with $\epsilon$ being 1, $\gt$ 0, $n^3*log_2(n)$ = $\Omega(n^{log_3(9) + 1}) $ or $n^3*log_2(n)$ = $\Omega(n^{3}) $
Now let's look at $a*f(\frac{n}{b})$.
$f(\frac{n}{b})$ = $f(\frac{n}{3})$ = $(\frac{n}{3})^3*log_2(\frac{n}{3})$, meaning $a*f(\frac{n}{b})$ = $\frac{1}{3} n^3log_2(\frac{n}{3})$
Breaking down $log_2(\frac{n}{3})$, we get
$\frac{1}{3} n^3log_2(\frac{n}{3})$ = $\frac{1}{3} n^3log_2(n) - \frac{1}{3} n^3log_2(3)$ which is $\leq \frac{1}{3} n^3log_2(n)$ or $cf(n)$ for which $c$ = $\frac{1}{3}$ which is less than 1.
Because this inequality will hold for all sufficiently large n, $T(n) \in \theta(n^3*log_2(n))$