# Algorithms: How do I sum O(n) and O(nlog(n)) together?

I have the follow algorithm which finds duplicates and removes them:

public static int numDuplicatesB(int[] arr) {
Sort.mergesort(arr);
int numDups = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] == arr[i - 1]) {
numDups++;
} }
return numDups;
}


I am trying to find the worst case time complexity of this. I know mergesort is nlog(n), and in my for loop I am iterating over the entire data set so that would count as n. I am unsure what to do with these numbers though. Should I just sum them together? If I were to do that, how would I do it?

• Side note: you could use a hash table to do this in O(n) depending on memory requirements. Oct 10, 2014 at 14:58

O(n) + O(n log(n)) = O(n log(n))


For Big O complexity, all you care about is the dominant term. n log(n) dominates n so that's the only term that you care about.

• Another way to think about this is to imagine your O(n) processing was really O(n log n), as though you did two independent sorts. Then you'd have 2 * O(n log n). But constants slough off, so you're back to O(n log n). Oct 8, 2014 at 21:57
• @Jonathan While that works in practice, it is very much true that O(n) is not equal to O(n log(n)), so I wouldn't advise using that on a regular basis.
– user91606
Oct 8, 2014 at 23:49
• @Emrakul actually I think the reasoning is theoretically sound as well as practical. O(n) is a proper subset of O(n log(n)). So if f(n) belongs to O(n) it also belongs to O(n log(n)). Oct 9, 2014 at 1:52
• It should be noted that when we say f(n) is O(g(n)) what we're really saying is that the function f is a member of the set of functions that grows at the rate of at most g(n) over the long term. This means all members of O(n) are also members of O(n*log(n)). The + in expressions like O(f(n)) + O(g(n)) actually refer to set union (which of you're really pedantic, you really should use ∪). Oct 9, 2014 at 10:57
• @LieRyan Originally, it is not set union, but set sum: A + B = { a + b | a in A, b in B }. It happens that for sets of the form O(g(n)) this is the same as set union, as one of the sets is always a subset of the other, and they both are invariant to sums (i.e. A + A = A). (Oops, Nate did write essentially the same). Oct 10, 2014 at 12:13

Let's reason our way through it and remember the definition of O. The one I'm going to use is for the limit at infinity.

You are correct in stating that you perform two operations with corresponding asymptotic bounds of O(n) and O(nlog(n)) but combining them into a single bound is not as simple as adding the two functions. You know your function takes at least O(n) time and also at least O(nlog(n)) time. So really the complexity class for your function is the union of O(n) and O(nlog(n)) but O(nlog(n)) is a superset of O(n) so really it is just O(nlog(n)).

• +1 this should be the answer. It describes the answer more precisely using compsci terms.
– user22815
Oct 9, 2014 at 0:16

If you were going to set it out longhand it would look roughly like this:

Suppose the total time is: a n + b n log(n), where a and b are constants (ignoring lower order terms).

As n goes to infinity (a n + b n log (n)) / n log (n) -> a / log (n) + b -> b

So the total time is O(b n log(n)) = O(n log (n)).

O (n log n) means "less than C n log n, if n is large".

O (n) means "less than D n, if n is large".

If you add both, the result is less than C n log n + D n < C n log n + D n log n < (C + D) n log n = O (n log n).

In general, if f (n) > C g (n) for large n and some C > 0, then O (f (n)) + O (g (n)) = O (f (n)). And after doing a few cases using the definition of O (), you'll know what you can and can't do.

The big O notation is defined as a set: So contains all functions that are - starting from some arbitrary large point - always smaller than g.

Now, when you have a function that is in and then execute another one that increases slower than g it is certainly increasing slower than 2g. So executing anything slower than g will not change the complexity class.

More formally: You can easily prove that.

TL;DR

It is still 