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)
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(log2𝑛 + log2𝑛) = O(2log2𝑛) = O(log2𝑛) = O(log𝑛)
Also the base of the logarithm is not relevant in Big O notation, so you can leave it out.