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?
 A: 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.
A: 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.
A: 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))$ 
