2
$\begingroup$

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))$.

$\endgroup$
  • 1
    $\begingroup$ "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"? $\endgroup$ – Charles Jul 29 '17 at 3:26
  • 6
    $\begingroup$ @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. $\endgroup$ – miracle173 Jul 29 '17 at 3:54
  • 1
    $\begingroup$ @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. $\endgroup$ – Charles Jul 29 '17 at 3:57
  • $\begingroup$ en.wikipedia.org/wiki/Big_O_notation $\endgroup$ – miracle173 Jul 29 '17 at 4:37
  • 5
    $\begingroup$ @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. $\endgroup$ – Raphael Jul 29 '17 at 6:27
3
$\begingroup$

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 constants 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$.

  • $2log(log(n)) \geq log(log(n))$
  • $3n\: log(n) \geq n\: log(n)$
  • $5log(n) \geq log(n)$

Rewriting,

$\quad f(n) = log(log(n)) + n\: log(n) + log(n)$,

where

$\quad 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))$

$\endgroup$
1
$\begingroup$

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))$.

$\endgroup$
  • $\begingroup$ @zaph The notation of this answer is correct. Depending on who is doing the writing, a can be used, or an $ $\endgroup$ – Charles Jul 30 '17 at 16:27
  • $\begingroup$ @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! $\endgroup$ – Charles Jul 30 '17 at 16:30
  • $\begingroup$ 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? $\endgroup$ – zaph Jul 30 '17 at 16:53
  • $\begingroup$ @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. :) $\endgroup$ – Charles Jul 30 '17 at 17:26
  • 1
    $\begingroup$ @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. $\endgroup$ – Charles Jul 30 '17 at 23:04
-1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ $\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. $\endgroup$ – miracle173 Jul 30 '17 at 20:17
  • 1
    $\begingroup$ Nevertheless your argument is correct. $\endgroup$ – miracle173 Jul 31 '17 at 4:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.