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: 302

Filed under:
|
|
|

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

Related posts about python

Related posts about algorithms