Confused with the complexity

Question

Im trying to find the time complexity of max1 and max2.

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

def max2(L, left, right):
    if left==right:
        return L[left]
    mid = (left+right)//2
    l = max2(L, left, mid)
    r = max2(L, mid+1, right)
    return max(l,r)

def max_list(L):
    return max1(L,0,len(L)-1)# or max2(L,0,len(L)-1)

From how I see it is that Max1:
depth is O(n). Each level of the recursion we do O(n-k). so overall the complexity is O(n^2). I read somewhere that the comlexity here is O(n). who's right?

max2:
depth is O(logn). Each step I do O(1) for every list and overal each step O(n) so I think Max2 is O(n)*O(logn)= O(nlogn). Somehow I read that it is O(n). so who's right?

Answer 1

Its important to define recursion complexity in terms of recurrence relations.

For your first algorithm, you have

T(n) = T(n-1) + O(1)

Which means you do some constant amount of work, and decrease the size of your set by 1 and recursively call yourself. This will yield a recursion tree of depth n, where each parent only has one child (you can think of it as a straight line), which you can see would be O(n) because of the constant amount of work.

For the second algorithm, you have

T(n) = 2T(n/2) + O(1)

Saying you split your input in half and call recursively twice, and do some constant amount of work. This scenario you can use the master thereom to show it is O(n).