# What is the big-O of the function 2 log(log n) + 3 n log(n) + 5 log(n)?

What is the big-O of the function $2\log(\log(n)) + 3n\log(n) + 5\log(n)$?
Is it just $O(n\log(n))$ for the whole function? I'm not sure how to represent $2\log(\log(n))$.

• "Big O" is time complexity that describes the worst case scenario.. so, you want to look for the term that will produce the highest values when considering values of n while approaching infinity. As for the other two terms, they will "fall to the side", or really, become so small in contrast to the overall resulting value that the terms are trivial to consider. So with that being said, which of the three terms will always produce the largest values "down the road"?
– user46712
Jul 29, 2017 at 3:26
• @Charles BigO is not a time complexity but a mathematical notation that describes how two real functions are related in respect to increasing arguments. It often will be used to describe the worst case running time of an algorithm but it also will be used to describe the average running time of an algorithm or anything else where I wanted to know how this "anything else" is bounded by a simple function if the argument increases. Jul 29, 2017 at 3:54
• @miracle173 No, Big O is worst case, Theta is average, and Omega is best case. They are classifications for time complexities that are described most simply by a single function that bounds the algorithm's worst run time scenario. I am familiar with this topic, but thank you. I was more trying to get the OP to answer their own question by offering leading questions and instructions on how to do so, than I was trying to give a wholesome definition of time complexity classifications.
– user46712
Jul 29, 2017 at 3:57
• en.wikipedia.org/wiki/Big_O_notation Jul 29, 2017 at 4:37
• @Charles "No, Big O is worst case, Theta is average, and Omega is best case." - No, no no no, NO! You couldn't be more wrong. Jul 29, 2017 at 6:27

Starting with an analytical assessment of the function's terms, we'll first format all terms as similarly as possible to each other, in order to more easily compare with one another. To do so, all constant factors will be removed, leaving only the variable elements of each term. This is acceptable to do since we're ultimately seeking Big-$$O$$ classification, which typically sets all constants within its expression to a value of $$1$$.

• $$2\log(\log(n)) \to \log(\log(n))$$
• $$3n\log(n) \to n\log(n)$$
• $$5\log(n) \to \log(n)$$

Rewriting,

$$\quad f(n) \to \log(\log(n)) + n\log(n) + \log(n)$$,

where $$n \in \mathbb{N}.$$

Now, since each term varies only by their logarithmic arguments, we can establish an inequality by direct comparison of those arguments, resulting in

$$\quad \log(\log(n)) \lt \log(n) \lt n \log(n),\ \forall n \gt 1$$

Therefore, it follows that

$$\quad f(n) \in O(n\log(n))$$

Please note that "the big-O of the function" isn't a correct formulation. We assume $\log$ is the binary logarithm $\log_2$. But actually the proof can be extended to any base.

We have

$$\log(x)\lt x, \forall x>0$$ and, if we plug in $\log(n)$ for $x$ $$\log(\log(n))\lt \log(n).\tag 1$$

Recall the definition of $f(n)=O(g(n))$: $$|f(n)|\le M |g(n)|,\forall n\ge n_0$$ for appropriate $M$ and $n_0$.

So if we choose $f(n)=\log(\log(n))$, $g(n)=\log(n)$, $M=1$ ,$n_0=2$

we see that $(1)$ is $$\log(\log(n))=O(\log(n))$$ and of course $$\log(\log(n))=O(n\log(n)).$$ So all three function in your expressions are $O(n\log(n))$ and therefore every linear combination of them $$a\log(\log(n)) + b \, n\log(n) + c\log(n), \quad a,b,c \in \mathrm R$$ is $O(n\log(n))$.

• @zaph The notation of this answer is correct. Depending on who is doing the writing, a can be used, or an $– user46712 Jul 30, 2017 at 16:27 • @zaph The notation of this answer is correct. When writing these expressions, an$=$can be used, as well as$\in$. Mathematicians tend to use$=$more, whereas I myself prefer$\in$set notation because I feel it's more descriptive of the situation. Both are perfectly acceptable though! – user46712 Jul 30, 2017 at 16:30 • If < is used in log(log(n)) < log(n) why not use < in log(log(n)) = O(log(n))? Wouldn't log(log(n)) < O(log(n)) be more consistent? – zaph Jul 30, 2017 at 16:53 • @zaph Please notice that the r.h.s. of the expressions you've questioned have$O()$. I believe your confusion stems from neglecting to recognize this. :) – user46712 Jul 30, 2017 at 17:26 • @zaph No worries. To pull off Wiki's page for Big O: "Note that "=" is not meant to express "is equal to" in its normal mathematical sense, but rather a more colloquial "is". So, you can read it as a property of the function. Ex: "He is a boy" :: "$f$is (has) a Big O of$n \: log(n)$". Or at least, that's how I perceive it. Critiques are welcome of course. – user46712 Jul 30, 2017 at 23:04 The best way to find big-o of a function like this: $$f(n) = \sum_{i=1}^k f_i(n)$$ is to find an i where: $$\forall j \in [1,k], j\neq i \rightarrow \lim_{n->\infty} \frac{f_j(n)}{f_i(n)} =0$$ therefor big-o is $$n\log(n)$$ •$\lim_\limits{n->\infty} \frac{f_j(n)}{f_i(n)} =0$is too restictive,$\lim_\limits{n->\infty} \frac{f_j(n)}{f_i(n)} <\infty$will be sufficient, too.$\lim_\limits{n->\infty}\sup \frac{f_j(n)}{f_i(n)} <\infty$is exact. And if$f_j(n)<f_i(n)\$ this is already sufficient, you dont have to calculate the limit. So in this case I can't see why it should be the best method. Jul 30, 2017 at 20:17
• Nevertheless your argument is correct. Jul 31, 2017 at 4:10

It is obvious that $$\log n\le an$$ for some constant $$a$$ because the number of digits of $$n$$ cannot exceed $$n$$. Then substituting $$n$$ for $$\log n$$, $$\log\log n\le a\log n$$. (For the base-2 logarithm, $$a=1$$ works.)

Combining, we have

$$2\log\log n+3n\log n+5\log n\le (2a+3n+5)\log n\le cn\log n$$ because for $$n\ge1$$ and $$c=2a+5+3$$,

$$\frac{2a+5}n+3\le c.$$

Yes, the expression is $$O(n \log n)$$. For large $$n$$, $$n \log n$$ dominates $$\log n$$ and $$\log \log n$$.