Before I goes into this, take a look of the binary search solutions, and understand them before you proceed reading.

All of these solutions (with minor variations) goes like this:

- Get the low bound value by choosing the max number from the array.
- Get the high bound value by summing all the numbers of the array.
- Perform a binary search between those values, and check if the solution is a valid split.

**The thing is, this binary search complexity is dependant on the actual values within the array, and not on the count of elements of the array.**

So, now you may be thinking, the complexity of the binary search phase (bin search + array check) should be: O (log(high_bound - low_bound) * n) , right?

Well, not exactly.

Let M = high_bound - low_bound.

In computer science, a complexity analysis is dependent on the **length** of the input. So actually if M is of length D bits, M = O(2^D).

So, the run time of the binary search phase is actually: O(log(M)*n) = O(log(2^D)*n) = O(D*n).

In the **real world**, this algorithm is still quite efficient (since the max number of bits in an integer is usually 32/64), but you should still be aware of how a correct complexity analysis is performed.

Further reading: Pseudo-polynomial time