I want to ask, I'm still learning about time complexity. I got a problem, the question asked me to calculate the time complexity of a binary search,
The time complexity of a binary search is O(log m).
After the search, they want me to calculate a linear O(n) search inside of it. So inside a binary search, there is a linear search.
Is it O(n log m) or O(log m*n)?
And if you could add, please tell me how to calculate the complexity if there is multiple algorithm combine. Thank you!
I'm not sure I fully understood you but I will do my best:
There are 2 possible scenarios which I think are relevant to your question:
There is a loop inside a loop, where one does not effect the other. In that case, you always multiply the time complexity of one by the other one's. In your case for example, if you follow a binary search in the external loop and a linear search inside, should be done in O(n*logn). The rule is relevant for 3 loops inside each other as well, etc. Just multiply one by another.
Some of the nested loops affect some others (ie. different iterations of an outer loop causes a change to the time complexity of an inner loop). In this case calculating the overall complexity of the nested loops becomes more complicated and the above method won't work.
Anyway I do not see any way to get O(log m*n) in your case.
Also, I did not really understand why you switched between n and m. Typically if you talk about the same data structure, with the same number of items, then you use n.