The recurrence relation $\forall n\in\mathbb{N}\cup\{0\}$ is $T(n)=\Theta(n^2)+2\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}{T(i)}$, with base case of $T(0)=0$.

Fairly simple tree analysis shows that $T(n)\in\Omega(n^3)$ and $T(n)\in O(n^{\log_2{n}})$.

But I want to find $f(n)$ for which $T(n)\in\Theta(f(n))$, or at least tighter lower and upper bounds.

  • $\begingroup$ Crossposting questions with such a small interval leads to duplicated effort from multiple communities. Please refer to the FAQ of each site for guidelines on crossposting. $\endgroup$
    – chazisop
    Dec 7, 2015 at 16:02
  • 1
    $\begingroup$ Also cross-posted at mathoverflow.net/questions/225423/… — this violates our cross-posting policy. $\endgroup$ Dec 8, 2015 at 3:14
  • $\begingroup$ Sorry, I didn't realize that. I removed this question from the other places. $\endgroup$ Dec 8, 2015 at 3:35

1 Answer 1


It is $n^{\Theta(\log n)}$, although I'm not sure exactly what the constant in the theta is. For the upper bound (the one you already have), note that, even without the $n^2$ term but with a base case of $1$ rather than $0$, this recurrence is dominated term-by-term by the recurrence $$U(n)=nU(\frac{n}{2}).$$ For the lower bound, note that it dominates the recurrence $$L(n)=\frac{n}{2}L(\frac{n}{4}).$$


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.