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?