$a)$ Determine for all pairs $i$ and $j$, $i,j ∈ \{1, \ldots, 6\}$ whether for the ones given below functions $f_i ∈ O(f_j)$ or $f_i ∈ o(f_j)$ or neither of the two applies as $n → \infty$:

$f_1 = \log(n),$

$f_2 = \log(\sqrt n),$

$f_3 = \log(n + \log(n)),$

$f_4 = \sqrt{\log(n)},$

$f_5 = \log\log(n^{\log(n)}),$

$f_6 = \log_2(n)$

$b)$ Show that for the functions $ f(n) = \log(n!) $ and $g(n) = n\log(n)$ it holds that $f ∈ O(g)$ and $g ∈ O(f)$. In fact, $f$ and $g$ are even asymptotically equivalent.

I am confused about the big $O$ and small $o$. When is $f_{i} ∈ O(f_j)$ and when is $f_i ∈ o(f_j)$? How to prove asymptotic equivalence?

  • 3
    $\begingroup$ See here a table with some common ways to define them. $\endgroup$ – plop Apr 19 at 20:51
  • 1
    $\begingroup$ Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Apr 19 at 22:09
  • 2
    $\begingroup$ Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Apr 19 at 22:09

The usual definitions are the following (assuming $f$ and $g$ are positive):

  • $f(n) \in O(g(n))$ if $f$ is eventually less that than some constant multiple of $g(n)$. In more mathematical terms $f(n) \in O(g(n))$ if there exists some $C > 0$ and $N \in \mathbb{N}$ such that $f(n) \leq C \cdot g(n)$ for all $n \geq N$.

  • $f(n) \in o(g(n))$ if $f$ is dominated by $g(n)$ as $n \to \infty$. Again, more formally, $f(n) \in o(g(n))$ if $\lim_{n\to \infty} \frac{f(n)}{g(n)} = 0$. (Notice that this is stronger than Big-O)

  • $f(n)$ and $g(n)$ are asymptoticaly equivalent if as $n$ grows $f(n)$ and $g(n)$ get very close to each other. The definition in terms of limits is that $\lim_{n\to \infty}\frac{f(n)}{g(n)} = 1$.

Let's examine $f_1$ and $f_2$ in your example. If you calculate the limits of $\frac{f_1(n)}{f_2(n)}$ and $\frac{f_2(n)}{f_1(n)}$ as $n\to \infty$ you'll see that neither is equal to 0 so $f_1 \not\in o(f_2)$ and $f_2 \not\in o(f_1)$.

Now notice that for all $n \geq 2$ we have $\sqrt{n} \leq n$ and since $\log$ is increasing $f_2(n) = \log(\sqrt{n}) \leq \log(n) = f_2(n)$ so $f_2 \in O(f_1)$. To see that $f_1 \in O(f_2)$ just write $\log(n)$ as $\log(\sqrt{n}^2) = 2\log(n)$.

For part b) a hint is given in another answer (this is actually the "proper" way to prove such things) but another approach would be to use Stoltz-Cesaro to prove that $\lim_{n\to \infty}\frac{\log(n!)}{n\log(n)}=1$ and deduct that this also implies that $f \in O(g)$ and $g \in O(f)$ using the limit definition.

  1. How many pairs we can choose from $1$ to $6$? I think, we can find someone to help you in couple, but all is a lot of work.
  2. Hint: we have

$$\left(\frac{n}{e}\right)^n \lt n! \lt e\left(\frac{n}{2}\right)^n$$


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.