<s>[INST] How to apply Master theorem to this relation? 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?
 [/INST] 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.
</s>