Big O when adding together different routines

Question

Lets say I have a routine that scans an entire list of n items 3 times, does a sort based on the size, and then bsearches that sorted list n times. The scans are O(n) time, the sort I will call O(n log(n)), and the n times bsearch is O(n log(n)). If we add all 3 together, does it just give us the worst case of the 3 - the n log(n) value(s) or does the semantics allow added times?

Pretty sure, now that I type this out that the answer is n log(n), but I might as well confirm now that I have it typed out :)

Answer 1

The sum is indeed the worst of the three for Big-O.

The reason is that your function's time complexity is

(n) => 3n + nlogn + nlogn

which is

(n) => 3n + 2nlogn

This function is bounded above by 3nlogn, so it is in O(n log n).

You can choose any constant. I just happened to choose 3 because it was a good asymptotic upper bound.