0
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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