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

CC BY-SA 3.0
2015-12-07T04:18:42.857Z
2015-12-07T04:18:42.857Z
David Eppstein
<p>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$.</p>

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

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

CC BY-SA 3.0
2015-12-07T16:02:00.400Z
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
CC BY-SA 3.0
2015-12-08T03:14:56.500Z
Also cross-posted at http://mathoverflow.net/questions/225423/how-can-i-find-tight-asymptotic-bounds-for-this-half-history-recurrence-relation — this violates our cross-posting policy.
David Eppstein
CC BY-SA 3.0
2015-12-08T03:35:56.973Z
Sorry, I didn't realize that. I removed this question from the other places.
user1145925
<time-complexity><recursion><asymptotics>
How can I find tight asymptotic bounds for this half-history recurrence relation?
user1145925
# How can I find tight asymptotic bounds for this half-history recurrence relation?

(Asked by: username_0 on 2015-12-07)

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.

**Tags:** time-complexity, recursion, asymptotics

> **Comments:**
> **username_1**: 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.  
> **username_2**: Also cross-posted at http://mathoverflow.net/questions/225423/how-can-i-find-tight-asymptotic-bounds-for-this-half-history-recurrence-relation — this violates our cross-posting policy.  
> **username_0**: Sorry, I didn't realize that. I removed this question from the other places.  

---

## 1 answers

### Answer by username_2 on 2015-12-07. Score: 1 | Accepted answer

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


---

