1
$\begingroup$

I have an algorithm with running time that satisfies $$ T(n) \leq n + \frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n-i)),$$ and $T(0) = 0$. I was able to show that $T(n) = \mathcal O(n\log n)$ with a leading constant $c > 4$.

I modified this algorithm such that the recursion for $T(n)$ now satisfies $$ T(n) \leq 3 \log n + n + \frac{3}{n}\sum^{2n/3}_{i=n/3}(T(i) + T(n-i)),$$ and $T(0) = 0$. Intuitively, this algorithm should also be $\mathcal O(n\log n)$ but with a better leading constant, but I haven't been able to show it. Any ideas?

Improve this question
$\endgroup$
4
  • $\begingroup$ "with a better leading constant": what do you mean ?? $\endgroup$
    – Yves Daoust
    Nov 2, 2022 at 7:31
  • $\begingroup$ What is your base case $T(0)$? $\endgroup$
    – AspiringMat
    Nov 2, 2022 at 22:00
  • $\begingroup$ @AspiringMatL T(0) = 0. $\endgroup$
    – Keio203
    Nov 3, 2022 at 14:54
  • $\begingroup$ @YvesDaoust: With 0< c < 4 $\endgroup$
    – Keio203
    Nov 7, 2022 at 17:19

0

Reset to default

Your Answer

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