Runtime analysis
Posted
by
Joe Smith
on Programmers
See other posts from Programmers
or by Joe Smith
Published on 2012-03-27T00:43:03Z
Indexed on
2012/03/27
5:39 UTC
Read the original article
Hit count: 329
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.
© Programmers or respective owner