# Solving recurrence relation $T(n) = \max\{T(k)+T(n−k)+O(\min\{k, n-k\})\}$

My question arises out of this competitive programming problem. The idea is to find a unique element $$u$$ and then divide-and-conquer for the subarray to the left and to the right of $$u$$.

Searching for the unique element naïvely in a single forward pass leads to an $$O(n^2)$$ algorithm. However, if we search from both ends simultaneously, we would have a recurrence relation shown in the title. Notably, it avoid the worst case scenario in the naïve algorithm. Does this improve the asymptotic time complexity?

It gives $$T(n) = O(n \log n)$$. Let's prove by induction that $$T(n) \le Cn \log n$$, for some big enough $$C \in \mathbb{R}$$:

The induction hypothesis is that $$T(n) \le C n \log n$$. Now take $$T(1) = 0$$ as the base case, notice that any $$C$$ satisfies the hypothesis. Now let's prove it for some $$n > 1$$, assuming the hypothesis is true for all $$1 \le k < n$$:

\begin{align*} (1) \quad T(n) &= \max_{1 \le k < n}\{T(k) + T(n-k) + O(\min(k, n-k))\} \\ (2) \quad T(n) &= \max_{1 \le k \le \frac{n}{2}}\{T(k) + T(n-k) + O(k)\}, \hspace{.5em} \text{by symmetry on k}\\ (3) \quad T(n) &\le \max_{1 \le k \le \frac{n}{2}}\{T(k) + T(n-k) + c k\} , \hspace{.5em} \text{for some } c \in \mathbb{R}\\ (4) \quad T(n) &\le \max_{1 \le k \le \frac{n}{2}}\{Ck \log k + C(n-k) \log (n-k) + ck\} \\ (5) \quad T(n) &\le C n \log n, \hspace{.5em} \text{for big enough }C \end{align*} And we have our proof by induction. Intuition in step $$(4) \to (5)$$, is that the function $$x \log x + (n - x) \log (n-x)$$ in $$[1, n-1]$$ is symmetric and convex ($$x \log x$$ is convex) maximizing at both ends, and choosing $$k=1$$ should maximize overall.

In order to prove $$(4) \to (5)$$, we want to show that $$C n \log n \ge C x \log x + C (n-x) \log (n-x) + cx \quad \forall x \in \left[1, \frac{n}{2}\right]$$ when $$C$$ is big enough. We do the following:

$$(C n \log n) - (C x \log x + C (n-x) \log (n-x) + cx) =$$ $$= (C x \log n + C (n-x) \log n) - (C x \log x + C (n-x) \log (n-x) + cx) =$$ $$= Cx(\log n - \log x) + C(n-x)(\log n - log (n-x)) - cx =$$ $$= Cx\left(\log \frac{n}{x}\right) + C(n-x)\left(\log \frac{n}{n-x}\right) - cx \ge$$ $$\ge Cx\log(2) - cx \ge 0, \hspace{.5em} \text{ when } C \gg c$$

• Well, you need to give a fixed $C$ from the start. And I don't see how you do that with your current argument - if you replace $O(\min(k, n-k))$ in your argument with $O(n)$, your "proof" doesn't seem affected. Commented Apr 28 at 0:29
• @Elucidase My fault! I guess now it's somehow correct. Commented Apr 28 at 1:17
• Why does $k=1$ maximizes $(4)$? Seems false to me: when $k=1$ for every $n$ we get $O(n)$ but when $k=n/2$ for every $n$ we get $O(n\log n)$. Commented Apr 28 at 1:51
• @Elucidase I added a proof for that, if I am not mistaken. Commented Apr 28 at 2:40
• Assuming $O(k)$ in $(2)$ is bounded starting from $k=1$, I think this works. Commented Apr 28 at 13:38