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

Improve this question
$\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
    Commented Mar 28, 2021 at 7:54
  • 1
    $\begingroup$ (I have taken the information hyperlinked not to be simply pirated.) $\endgroup$
    – greybeard
    Commented Mar 28, 2021 at 7:56

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the great answer. $\endgroup$
    – ABC
    Commented Apr 1, 2021 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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