# Run-time of a summation function and its complexity

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?

• 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.
– D.W.
Dec 19 '20 at 0:41

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