So for example I have this sorted array of x amount of Key, Value pairs(tuples). I have a method called range which takes 2 arguments, the first is the first key to find and the second is the last key to find. This function returns all of the keys between the two. So range uses binary search to find the first element and once it does, it uses linear search to go until the last key has been found. I thought this entire thing would have a runtime of O(log(n)) but now I am second guessing myself as it takes longer to execute than I'd like. So my question is what would be the runtime of this function since I seem to be mistaken?

CodePudding user response：

worst-case complexity - [O(log(n)) O(n) = O(n)]

just think of a case where first key is index-1 and second one is index-n in worst case scenario.