What is the running time complexity and space complexity of

What is the running time complexity and space complexity of the following procedure (n = R - L + 1). Explain your answer. def foo(V, L, R): if L==R: return V[L] mid = (L+R)//2 m1 = foo(V, L, mid) m2 = foo(V, mid+1, R) if m1==m2: return ml count1, count2 = 0, 0 for i in range(L, R+1): if V[i] == ml: count1 += 1 if V[i] == m2: count2 += 1 if count 1 > (R-L+D/2: return ml if count2 > (R-L+D/2: return m2 return None

Solution

We are removing half the data at each turn so time complexity is O(log n).

We divide it into 2 till we find 1. Thus,

1= N/2^x

2^x = N

Thus x = log₂ n