# How can I find tight asymptotic bounds for this half-history recurrence relation?

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.

• 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. – chazisop Dec 7 '15 at 16:02
• Also cross-posted at mathoverflow.net/questions/225423/… — this violates our cross-posting policy. – David Eppstein Dec 8 '15 at 3:14
• Sorry, I didn't realize that. I removed this question from the other places. – user1145925 Dec 8 '15 at 3:35

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}).$$