CODEWITHSUNDEEP
algorithmbig-o
Michael Dorgan
Michael Dorgan

Reputation: 12515

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 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 :)

Upvotes: 5

Views: 2507

Answers (4)

Ray Toal
Ray Toal

Reputation: 88428

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.

Upvotes: 10

James Wilcox
James Wilcox

Reputation: 5663

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.

Upvotes: 0

alun
alun

Reputation: 3441

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.

Upvotes: 0

AustinDahl
AustinDahl

Reputation: 852

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

Upvotes: 2

Related Questions