# two recursive functions that take a list and return its maximum value
# both use slicing and are therefore inefficient, time-wise and memory-wise
# recursion depth: O(n), complexity: O(n^2)
def max1(L):
if len(L)==1:
return L[0]
return max(L[0],max1(L[1:]))
# recursion depth: O(log(n)), complexity: O(nlog(n))
def max2(L):
if len(L)==1:
return L[0]
l = max2(L[:len(L)//2])
r = max2(L[len(L)//2:])
return max(l,r)