What is the time complexity of doing two binary searches on an array?

Question

I have a function which operates on a list of ordered times. The function is passed a certain time as a parameter and it returns the number of times that specific time appears in the array.

My function performs two binary searches on the list, one to find the upper bound of a specific time, and one to find the lower bound.

What would be the time complexity of this function? I know that binary search has a time complexity of log2(n) but I'm unsure how doing it twice would affect the time complexity. Is it just log2(2n)?

    def count_time(time):

        return self.upper_bound(time) - self.lower_bound(time)

Answer 1

Performing two binary searches instead of one will not affect asymptotic complexity; it is just a factor 2 (not for , but for the logarithm) which you can omit:

O(log₂ + log₂) = O(2log₂) = O(log₂) = O(log)

Also the base of the logarithm is not relevant in Big O notation, so you can leave it out.

Answer 2

You are doing binary search two times on an array of ordered elements. Each time the asymptotic time complexity would be O(log2(n)). So the total time taken would be 2 * O(log2(n)). In asymptotic time complexity, the factor (2 in this case)is generally ignored if it's a constant value. So the answer is O(log2(n)).

It will not be ignored if this factor increases or decreases with the number of elements, i.e if the factor is directly proportional to the number of elements.