# Runtime of this algorithm

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?

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