Search code examples
algorithmtime-complexitymaster-theorem

How to apply master theorem of 2 binary search?

In order to count occurences of a number in a sorted array, I'm using a binary search twice

The recurrence relation of a binary search is T(N/2)+1 by calling it twice, is it correct to say it's 2T(N/2) +2 ?

But using master theorem the result I'm getting is O(n) which is wrong

def NbOcc(T,v) :
bg=Bg(T,0,len(T)-1,v) // T(N/2) +1
bd=Bd(T,0,len(T)-1,v) // T(N/2) +1
if bg>bd :
    return 0
else :
    return bd-bg+1
Solution

  • Bg and Bd functions are not a recursive call of NbOcc function. Hence, the time complexity of the NbOcc function is T(n) = TBG(n-1) + TBD(n-1) + 1 such that TBG and TBD are time complexity of Bg and Bd functions respectively.

    Now if both Bg and Bd functions are a binary search function, their time complexity will be in O(log(n)). Therefore, we can say T(n) is in O(log(n)).

    In sum, you made a mistake in the recurrent formula as they are not a recursive call. Thus, you shouldn't have used the master theorem as it cannot be applied in your case (only applicable for analysis of the binary search inside each Bg and Bd functions depending on their implementations).