Linear (?) Complexity of circular max subsum

#1

Hello.
In EPI the problem 17.11 which is to find the max subsum of a circular array.
For each i in n , we are to sweep across the array (up to i, then from i onward)…

The complexity is said to be linear but the solution looks roughly as such:
for (i = 1 -> n)
max[i]=maxSubsumEndingHere + MaxSubsumFromHereToN

Each of those maxSubsum function are O(n) and we do n of them… how can the total time be O(n) and not O(n^2) ?

Thanks.

0 Likes
#2

Hey,

I am not very sure which algorithm you mentioned required O(n^2) time. I have listed both algorithms in our book below, and could you kindly pointed that out:

https://github.com/epibook/epibook.github.io/blob/master/solutions/cpp/Maximum_subarray_in_circular_array.cc
https://github.com/epibook/epibook.github.io/blob/master/solutions/cpp/Maximum_subarray_in_circular_array_constant_space.cc

Both algorithms take O(n) time only as you can see clearly in the code.

0 Likes
#3

Thanks
I was more referring to the actual description p.405, l.4 than the code: "[…] we compute for each i the max subarray that starts a 0 and […].] and the max subarray ends at the last element"
Since the max subarray algorithm is O(n) (as recalled on the 4th line of the solution to this problem) and we run it for each i, I concluded that it was O(n*n).
But maybe looking at the code would make me see my mistake.
Thanks

0 Likes
#4

I see, the computation of that is done by two independent loops where maximum_begin and maximum_end are computed separately. In the future, we will explain this part in a more high-level idea which shall be much more easily understandable.

0 Likes