Solving $T(n)=3T(\lfloor \frac{n}{3}\rfloor) +2n\log n$ I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$
with base case $T(n) = 1$ if $n \leq 1$.
I am sure that the Master Theorem does not work. I am trying a lot with the substitution method, but I am very frustrated since I can't find a solid expression. Does any one have a good &quot;hint&quot; or good idea on how to solve this in a nice way?
Ignoring floors (see, e.g., the paragraph &quot;Ignoring Floors and Ceilings Is Okay, Honest&quot; in Chapter 1 of Algorithms for a discussion), your recurrence is of the form
$$
T(n) = aT(n/b) + f(n),
$$
with $a=b=3$ and $f(n) = 2 n \log n$.
You can then immediately apply the master theorem since, for $k=1$, $f(n) \in \Theta(n^{\log_b a} \log^k n) = \Theta(n \log n)$.
The solution to the recurrence is then:
$$
T(n) \in \Theta(n^{\log_b a}  \log^{k+1} n) = \Theta(n \log^2 n).
$$