1
$\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 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 "hint" or good idea on how to solve this in a nice way?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The master theorem gives the solution: $T(n) = \Theta(n\log^2 n)$. See Wikipedia. Wikipedia might not mention it, but the master theorem holds even if there are floors and ceilings, and even more generally, as demonstrated by its generalization, the Akra–Bazzi theorem. $\endgroup$
    – Yuval Filmus
    Nov 29, 2020 at 17:29
  • $\begingroup$ Even if there woluld be none floors or ceilings, the master theorem would not work. $2nlog(n)$ grows faster then $n$ and $n^j$ grows faster then $2nlog(n)$ ., for $j>0$ $\endgroup$
    – Frank
    Nov 29, 2020 at 17:54

1 Answer 1

Reset to default
2
$\begingroup$

Ignoring floors (see, e.g., the paragraph "Ignoring Floors and Ceilings Is Okay, Honest" 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). $$

Improve this answer
$\endgroup$

Your Answer

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

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