Complexity Analysis
def find_max(arr):
mx = arr[0]
for x in arr:
if x > mx:
mx = x
return mxWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(n)
Space
O(1)
How to derive it
One pass through all n elements. Each iteration does constant work (one comparison, one possible assignment). Only one extra variable `mx` is used regardless of input size.