# Postive interval problem lower bound

I was trying to solve the question given below.

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

• Do you actually mean whether there is an algorithm runs better than $\mathcal O(n\log n)$? Dec 23, 2018 at 13:38
• @Apass.Jack yes
– user94342
Dec 23, 2018 at 13:40
• @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)$". Dec 26, 2018 at 10:56
• 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]]. Dec 26, 2018 at 12:55
• @Elirsouag: Check the maximum subset sum algorithm Maximum subarray problem/Kadane's algorithm? close enough guess I don't see that. Dec 26, 2018 at 12:57