# Time complexity about Maximum subarray

I recently came across a function called the strawman algorithm which the pseudo code looks like this:

StrawmanSubarray(A):
Initialize bestsum = A[0]
For left=0 to n-1:
For right = left to n-1:
Compute sum A[left] + . . . + A[right]
If sum > bestsum: bestsum = sum


The time complexity is Θ (n^3), and I don't quite get where is the 3rd n comes from to get Θ (n^3)?

• How many operations can computing $A[left]+...+A[right]$ be? – BearAqua Aug 25 '20 at 20:24
• You're wrong; it matters. It is exactly what causes your confusion. – BearAqua Aug 25 '20 at 20:28
• You have right-left-1 sums in the line that starts with Compute . This line is repeated by the inner for for right = left to n-1 and the outer for repeats its content for left=0 to n-1. So, the number of sums is $\sum_{l=0}^{n-1}\sum_{r=l}^{n-1}(r-l-1)=\frac{n (n^2 - 3 n - 4)}{6}$. However, the line Compute could be implemented in such a way that each iteration does only one sum. In this case the number of sums is $\sum_{l=0}^{n - 1}( \sum_{r=l}^{n - 1} 1) = \frac{n (n + 1)}{2}$. – plop Aug 25 '20 at 20:31
• @BearAqua ok sure, let's assume the array length is n=8? – sctts-lol Aug 25 '20 at 20:32
• @plop sorry I am still a newbie, how do you get the formula n(n^2-3n-4)/6? thanks – sctts-lol Aug 25 '20 at 20:40