I was trying to solve the question given below.

enter image description here

Algorithm :

Using divide and conquer technique, divide the input till we get a very small size array's ( let us say of size 2 ). Solve these small size array's in a brute force way. In the Merge phase it will take $\mathcal{O}(n)$ time to sum both arrays, if we get a positive sum then one contigious array will be sufficient to cover all positive numbers.

Runtime : $T(n)=2T(n/2)+\mathcal{O}(n)$

Which implies $\mathcal{O}(n\log n)$ runtime Algorithm.

Question: How to prove that one can't solve the above problem in time better than $\mathcal{O}(n\log n)$?

  • $\begingroup$ Do you actually mean whether there is an algorithm runs better than $\mathcal O(n\log n)$? $\endgroup$
    – John L.
    Commented Dec 23, 2018 at 13:38
  • $\begingroup$ @Apass.Jack yes $\endgroup$
    – user94342
    Commented Dec 23, 2018 at 13:40
  • $\begingroup$ @I_wil_break_wall, $T(n)=T(n/2)+\mathcal{O}(n)$ means $T(n)=\mathcal O(n)$. It looks like you missed a factor of 2, "$T(n)=2T(n/2)+\mathcal{O}(n)$". $\endgroup$
    – John L.
    Commented Dec 26, 2018 at 10:56
  • 1
    $\begingroup$ I don't see why the algorithm you give works.. In the merge phase, you imply we either want to resolve the two halves independently or take the whole interval. But it might be possible the optimal solution uses an interval that overlaps with the midpoint and yet is not the whole segment. Consider [1 -2 3 -3 -3 3 -2 1]. The optimal solution is [[1] -2 [3 -3 -3 3] -2 [1]]. $\endgroup$ Commented Dec 26, 2018 at 12:55
  • $\begingroup$ @Elirsouag: Check the maximum subset sum algorithm Maximum subarray problem/Kadane's algorithm? close enough guess I don't see that. $\endgroup$
    – greybeard
    Commented Dec 26, 2018 at 12:57


Your Answer

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