I am trying to analyze the running time of the following function:

def algo(array: List[int]):
    x = 1
    y = 0
    sigma = 0
    for ix in range(1, len(array)):  #len(array) always >= 1
        summation = 0 
        for jx in range(ix, 0, -1):
            summation = summation + array[jx]
            if summation > sigma:
                x = jx
                y = ix 
                sigma = summation
    return (x,y)

I have identified a basic unit of the algorithm to count as the number of iterations/total loops, $L$, it runs through. So for instance, if the length of array, $n$, is $1$, then $L = 1$. If, $n = 5$, then $L = 15$. The pattern follows that of the triangular numbers sequence. If you plot a set of points $(n, L)$ you will see that it kind of looks exponential. Is my line of thinking so far okay?

  • 1
    $\begingroup$ Please don't delete a question after you've received an answer. That can be considered impolite. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to you but also to others in the future. Answerers might be responding on that basis, and deleting the question is counter to those goals. Thank you. $\endgroup$
    – D.W.
    Dec 19 '20 at 0:41

The body of the inner for loop is executed in constant time per iteration and it does not affect the number of iterations of the outer loops.

Let $n$ be the length of array. The outer for loop iterates $n$ times. During the $i$-th iteration of the outer loop, the inner for loop iterates $i$ times.

The overall time complexity is therefore: $$ \Theta(1) \cdot \sum_{i=1}^{n} i = \Theta(1) \cdot \Theta(n^2) = \Theta(n^2). $$


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.