# Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem

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 know that the solution is(with the help of the Master Theorem) $$\Theta(n*log^2(n))$$ I tried without the Master theorem and witht the help of the substuition method I got the following expression $$T(n)=n+2*n*\sum_{k=0}^{log_{3}(n)-1}log(\frac{n}{3^k})$$

How can I convert this expression into a valid $$\Theta(n*log^2(n))$$ expression ?

• You have a similar question here:‌ cs.stackexchange.com/q/132801/64229 – OmG Dec 2 '20 at 15:02
• similar yes, but actually completly different questions. – Frank Dec 2 '20 at 15:06

## 2 Answers

Let's suppose $$n=3^k$$. Then we have: $$T(n)=3^kT(1)+2n\log \frac{n^k}{3^{k-1}\cdots3^0}=n+2n\log 3^{k^2-\frac{k(k-1)}{2}} =\\ =n+2n\log n \cdot \frac{\log_3 n+1}{2}$$ Hope it helps.

T(n)=3T(⌊n3⌋)+2nlogn By substitution method  