Big O when adding together different routines

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 开发者_JS百科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 :)

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.

You are correct. When n gets really big, the n log(n) dominates 3n.

Yes it will just be the worst case since O-notation is just about asymptotic performance.

This should of course not be taken to mean that adding these extra steps will have no effect on your programs performance. One of the O(n) steps could easily consume a huge portion of your execution time for the given range of n where your program operates.

As Ray said, the answer is indeed O(n log(n)). The interesting part of this question is that it doesn't matter which way you look at it: does adding mean "actual addition" or does it mean "the worst case". Let's prove that these two ways of looking at it produce the same result.

Let f(n) and g(n) be functions, and without loss of generality suppose f is O(g). (Informally, that g is "worse" than f.) Then by definition, there exists constants M and k such that f(n) < M*g(n) whenever n > k. If we look at in the "worst case" way, we expect that f(n)+g(n) is O(g(n)). Now looking at it in the "actual addition" way, and specializing to the case where n > k, we have f(n) + g(n) < M*g(n) + g(n) = (M+1)*g(n), and so by definition f(n)+g(n) is O(g(n)) as desired.