CODEWITHSUNDEEP
pythontime-complexity
Art
Art

Reputation: 275

What is the time complexity of this function using a built-in function?

Assume you have the following compute function, using python built-in sum function: 

def compute(a_list):
    for i in range(0, n):                        #Line 1
        number = sum(a_list[0:i + 1])/(i+1)      #Line 2
    return number

What would the time-complexity for something like this look like?

Line 1 is executed n number of times, but Line 2, having the built-in sum function (O(n)), would it execute n^2 number of times? Therefore the algorithm would be O(n^2).

For each iteration of i, Line 2 is executed 1 + 2 + 3 + ... + n-2 + n-1 + n. The sum of these terms is

enter image description here

Is this correct?

Upvotes: 0

Views: 153

Answers (1)

Sam Mason
Sam Mason

Reputation: 16213

I'd say that line 1 is executed once, and this causes line 2 to be executed n times. the list subscript is O(n), and the sum is also O(n). division, addition and assignment are all O(1).

compute is therefore O(N^2) as the largest terms are evaluating an O(n) operation O(n) times.

note that, as written, it discards all intermediate results, so it could be rewritten as:

def compute(a_list):
    return sum(a_list[0:n])/n

which would be O(n).

Upvotes: 1

Related Questions