0
$\begingroup$

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 ?

Improve this question
$\endgroup$
3
  • $\begingroup$ You have a similar question here:‌ cs.stackexchange.com/q/132801/64229 $\endgroup$
    – OmG
    Commented Dec 2, 2020 at 15:02
  • $\begingroup$ similar yes, but actually completly different questions. $\endgroup$
    – Frank
    Commented Dec 2, 2020 at 15:06
  • $\begingroup$ Our reference questions may have some methods for you. $\endgroup$
    – Raphael
    Commented May 31, 2021 at 20:13

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Page 1

Page 2

Improve this answer
$\endgroup$
1
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$
    – Raphael
    Commented May 31, 2021 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.