<s>[INST] Can Master Theorem be applied on any of these? 1) $T(n) = 6T(n/2) + 2^{3 \log(n)}$
2) $T(n) = 8T(n/2) + \frac{n^3}{(\log(n))^4}$
3) $T(n) = 9T(n/3) + n(\log(n))^3$
Can the complexity for these be calculated with the Master Theorem?
I am not sure how to decide upon which case they fit in.
 [/INST] For problem three, lets solve the recurrence
$$T(n) = 9 T(\lfloor n/3\rfloor) + n \times (1+\lfloor\log_3 n\rfloor)^3$$
where we set $T(0)=0.$
Let the base three representation of $n$ be
$$n = \sum_{k=0}^{\lfloor\log_3 n\rfloor} d_k 3^k.$$
Then we get the exact formula
$$T(n) = \sum_{j=0}^{\lfloor\log_3 n\rfloor} 9^j \times 
(1+\lfloor\log_3 n\rfloor- j)^3 \times 
\sum_{k=j}^{\lfloor\log_3 n\rfloor} d_k 3^{k-j}
\\ = \sum_{j=0}^{\lfloor\log_3 n\rfloor} 3^j \times 
(1+\lfloor\log_3 n\rfloor - j)^3 \times 
\sum_{k=j}^{\lfloor\log_3 n\rfloor} d_k 3^k .$$
Now for an upper bound consider a string of two digits, which gives
$$T(n)\le \sum_{j=0}^{\lfloor\log_3 n\rfloor} 3^j \times 
(1+\lfloor\log_3 n\rfloor - j)^3 \times 2 \times
\sum_{k=j}^{\lfloor\log_3 n\rfloor} 3^k
\\ =  \sum_{j=0}^{\lfloor\log_3 n\rfloor} 3^j \times 
(1+\lfloor\log_3 n\rfloor - j)^3 \left(3^{\lfloor\log_3 n\rfloor + 1}-3^j\right)
\\ = \sum_{j=1}^{\lfloor\log_3 n\rfloor+1} 
3^{\lfloor\log_3 n\rfloor+1-j} \times j^3 \times
\left(3^{\lfloor\log_3 n\rfloor + 1}-3^{\lfloor\log_3 n\rfloor + 1- j}\right)
\\ = 3^{2(\lfloor\log_3 n\rfloor + 1)}
\sum_{j=1}^{\lfloor\log_3 n\rfloor+1} 3^{-j} j^3 (1- 3^{-j}).$$
Now the sum term converges to a constant and we get the upper bound
$$\frac{7917}{2048} \times 3^{2(\lfloor\log_3 n\rfloor + 1)}.$$
For the lower bound take a one followed by a string of zeros, which gives
$$T(n)\ge \sum_{j=0}^{\lfloor\log_3 n\rfloor} 3^j \times 
(1+\lfloor\log_3 n\rfloor - j)^3 \times 3^{\lfloor\log_3 n\rfloor}
\\ = 3^{\lfloor\log_3 n\rfloor} 
\sum_{j=1}^{\lfloor\log_3 n\rfloor+1} 3^{\lfloor\log_3 n\rfloor +1 -j} \times 
j^3
=  3^{2\lfloor\log_3 n\rfloor + 1} \sum_{j=1}^{\lfloor\log_3 n\rfloor+1} j^3 3^{-j}.$$
The sum term again converges to a constant and we get for the lower bound asymptotics the formula
$$\frac{33}{8}  3^{2\lfloor\log_3 n\rfloor + 1} .$$
Note that for the upper bound we have $\lfloor\log_3 n\rfloor+1\to\log_3 n,$ so that it is in fact $$\frac{7917}{2048} n^2 \approx 3.86572265625\times n^2$$ but for the lower bound $\lfloor\log_3 n\rfloor = \log_3 n$, so that it is $$\frac{33}{8} \times 3 \times n^2 = \frac{99}{8} n^2 \approx 12.375 \times n^2.$$
Joining the two bounds we may conclude that $$T(n)\in 
\Theta\left(3^{2\lfloor\log_3 n\rfloor}\right) = \Theta(n^2).$$
A similar computation which is a bit simpler can be used to analyse the cost of Strassen matrix multiplication.
</s>