0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ How many operations can computing $A[left]+...+A[right]$ be? $\endgroup$ – BearAqua Aug 25 '20 at 20:24
  • $\begingroup$ You're wrong; it matters. It is exactly what causes your confusion. $\endgroup$ – BearAqua Aug 25 '20 at 20:28
  • $\begingroup$ 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}$. $\endgroup$ – plop Aug 25 '20 at 20:31
  • $\begingroup$ @BearAqua ok sure, let's assume the array length is n=8? $\endgroup$ – sctts-lol Aug 25 '20 at 20:32
  • $\begingroup$ @plop sorry I am still a newbie, how do you get the formula n(n^2-3n-4)/6? thanks $\endgroup$ – sctts-lol Aug 25 '20 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.