# Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o

New to the board, if this is the wrong section I apologize and I will delete it. Will be helpful to be provided correct exchange to guide me through this process of learning.

If you have a given an array such as A[1...n] of numeric values (can be positive, zero, and negative) how may you determine the subarray A[i...j] (1≤ i ≤ j ≤ n) where the sum of elements is maximum overall (subvectors). Regarding the brute force algorithm below, how do you go about analyzing its best case, worst case, and average-case time complexity in terms of a polynomial of n and the asymptotic notation of ɵ. How would you even show steps? Without building out the algorithm?

Thanks in advance.

// PSEUDOCODE
// BRUTE-FORCE-FIND-MAXIMUM-SUBARRAY(A)
n = A.length
max-sum = -∞
for l = 1 to n
sum = 0
for h = l to n
sum = sum + A[h]
if sum > max-sum
max-sum = sum
low = l
high = h
return (low, high) # No, return of MAX-HIGH


Note: New to the forum, not sure if this is the correct exchange. But I am referring to and referencing problems from https://walkccc.me/CLRS/Chap04/4.1/.

• (There are recommendations about names. Such as not using small L in a context where "Arabic" 1 may feature, or I with unary/Roman.) – greybeard Mar 28 at 7:54
• (I have taken the information hyperlinked not to be simply pirated.) – greybeard Mar 28 at 7:56

## 1 Answer

Your algorithm goes over all pairs $$(\ell,h)$$ of indices such that $$1 \leq \ell \leq h \leq n$$, and for each of them, runs $$\Theta(1)$$ operations (the rest of the steps are insignificant from an asymptotic point of view). If there are $$M$$ such pairs, then the best case, worst case, average case complexity are all equal to $$\Theta(M)$$.

• Thanks for the great answer. – ABC Apr 1 at 1:33