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. Dec 23 '18 at 13:38
  • $\begingroup$ @Apass.Jack yes $\endgroup$ – user94342 Dec 23 '18 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. Dec 26 '18 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$ – Timon Knigge Dec 26 '18 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 Dec 26 '18 at 12:57

Your Answer

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