1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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$$

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Elucidase
    Commented Apr 28 at 0:29
  • $\begingroup$ @Elucidase My fault! I guess now it's somehow correct. $\endgroup$
    – izanbf1803
    Commented Apr 28 at 1:17
  • $\begingroup$ 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)$. $\endgroup$
    – Elucidase
    Commented Apr 28 at 1:51
  • $\begingroup$ @Elucidase I added a proof for that, if I am not mistaken. $\endgroup$
    – izanbf1803
    Commented Apr 28 at 2:40
  • 1
    $\begingroup$ Assuming $O(k)$ in $(2)$ is bounded starting from $k=1$, I think this works. $\endgroup$
    – Elucidase
    Commented Apr 28 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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