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

Question

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/.

• greybeard: (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: (I have taken the information hyperlinked not to be simply pirated.)

Answer 1

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

• ABC: Thanks for the great answer.