Runtime analysis
- by Joe Smith
can someone please help me with the analysis of the following function (for inputs of size n).
The part that confuses me the most is the inner for loop.
def prefix_sums(L): # Total cost = ?
pSum = [] #cost = 1
for a in range(len(L)+1): # range + body of function = (n+1) + (n+1)*(body) ?
s = 0 #cost = 1
for b in range(a): # cost = ?
s = s + L[b] #cost = operation + accessing list = 2
pSum.append(s) #cost = 1
return pSum #cost = 1
What I need to do is figure out the cost of each statement.
