Brute Force Complexity of Maximum Sub Array sum problem

#1

In Page 33 of the 1025 edition, is is stated that the brute force complexity for finding the maximum sub array sum is O(n^3). But there are only sigma(n)= O(n^2) sub-arrays. So even brute force should have a complexity of O(n^2).

I am unable to understand why the brute force solution requires O(n^3) time

0 Likes
#2

there are O(n^2) subarrays, but each subarray sum calculation takes O(n) w/ no optimization

– given subarray from index i to j, you will read all elements between the two indices and add them up.
– repeat for O(n^2) subarrays.

so O(n^3) overall for brute-force if no optimization done.

0 Likes