python,max,time-complexity,complexity-theory , Finding the complexity of a function

## Question:

Tag: python,max,time-complexity,complexity-theory

I am trying to calculate the time complexity of the next function, `max_list11`, which finds a maximum of a list recursively:

``````def max11(L,left,right):
if left==right:
return L[left]
return max(L[left], max11(L,left+1,right))

def max_list11(L):
return max11(L,0,len(L)-1)
``````

From what I found out, the time complexity should be `O(n)`, since what the function does is `n` times max of 2 objects list, although when I calculate running times I get polynomial growth in the running times (apparently `O(n²)`), and I wonder why is that.

I've time the function this way:

``````def elasped(f,L):
t0 = time.clock()
s = f(L)
return(time.clock()-t0)

def avg_elasped(f,L,times = 100):
measurements = []
for i in range(times):
measurements += [elasped(f,L)]
return sum(measurements)/times
``````

and then I've tried 1000, 2000, .... , 10000 long lists.