1
$\begingroup$

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

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

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

$\endgroup$
1
  • $\begingroup$ Thanks for the great answer. $\endgroup$ – ABC Apr 1 at 1:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.