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

// 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.) Commented Mar 28, 2021 at 7:54
• (I have taken the information hyperlinked not to be simply pirated.) Commented Mar 28, 2021 at 7:56

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)$$.