1
$\begingroup$

I have the following statement. I would say it's correct as it's either equal or higher than $\Omega(\log^{10}(n))$.

Because: I know $\log(2^n) = n$. By that I would guess the same goes for $\log(n^{10})$ unimportant if the number is higher or not. By that it should be n. With this knowledge we already know it's higher than our $\Omega(\log^{10}(n))$.

We also know $\log(n)^2 = \log(n)$ again it will be higher or equal to our omega.

Is this correct?

$$(3 \log^2 n + 55 \log(n^{10}) + 8 \log n) \cdot \log n = \Omega(\log^{10} n)$$

$\endgroup$
5
  • 1
    $\begingroup$ Is $\log^2 n$ supposed to mean $(\log n)^2$ or $\log \log n$? $\endgroup$
    – dkaeae
    May 14, 2019 at 11:25
  • $\begingroup$ Yes it is @dkaeae $\endgroup$ May 14, 2019 at 11:43
  • $\begingroup$ @BorisGrunwald $(\log n)^2$ and $\log \log n$ are not the same thing. $\endgroup$
    – dkaeae
    May 14, 2019 at 12:06
  • $\begingroup$ "$\log(𝑛)^2=\log(𝑛)$" This statement is untrue. If you meant $\log \log n$, then $\log n = \Omega (\log \log n)$ and if you meant $\log (n) \log (n)$ then $\log (n) = O(\log(n)\log(n))$. $\endgroup$ May 14, 2019 at 12:46
  • $\begingroup$ $\log(2^𝑛)=𝑛$ is also an imprecise statement here, since you didn't explicitly specify the base. While it's true in terms of asymptotics, the constant factor cannot be ignored if you simply use the equal sign. $\endgroup$ May 14, 2019 at 12:48

2 Answers 2

1
$\begingroup$

Don't guess, but look at the definition which tells you that in order for $f(n) = \Omega(g(n))$ to hold, it must be the case that $\lim_{n \to \infty} f(n)/g(n) > 0$.

If I plug in $f(n)$ and $g(n)$ according to your description, I think I will get $\lim_{n \to \infty} f(n)/g(n) = 0$. You should check whether I made a mistake and draw the appropriate conclusions.

$\endgroup$
1
  • $\begingroup$ In my computation, I assumed that $\log^k n$ means $(\log(n))^k$. $\endgroup$
    – Juho
    May 14, 2019 at 11:34
1
$\begingroup$

When $\log^k(n) = \log (\log (...\log(n)))$,

$$(3 \log^2 n + 55 \log(n^{10}) + 8 \log n) \cdot \log n \\ = \Theta((\log^2(n)+\log(n)+\log(n))\log(n)) \\ = \omega(\log^3(n)).$$

In fact, anything growing strictly slower than $\log(n)\log\log(n)$ will hold inside the $\omega$, so $\log^{10}(n)$ will also fit.

When $\log^k(n)=(\log(n))^k$, $$(3 \log^2 n + 55 \log(n^{10}) + 8 \log n) \cdot \log n \\ = \Theta(\log^2(n)+\log(n)+\log(n))\cdot \log(n) \\ =\omega(\log(n)).$$

To see the big-$\Theta$ bounds are correct, verify that $$\lim_{n\rightarrow \infty} \frac{(3 \log \log n + 55 \log(n^{10}) + 8 \log n) \cdot \log n}{(\log \log(n) + \log(n)+\log(n))\log(n)}=O(1).$$ $$\lim_{n\rightarrow \infty}\frac{(3 \log(n)\log(n) + 55 \log(n^{10}) + 8 \log n) \cdot \log n}{(\log(n)\log(n)+\log(n)+\log(n))\cdot \log(n)}=O(1).$$

To see the $\omega$ bounds are correct: $$\lim_{n\rightarrow \infty}\frac{(3 \log\log n + 55 \log(n^{10}) + 8 \log n) \cdot \log n}{\log\log\log(n)}=\infty.$$ $$\lim_{n\rightarrow \infty}\frac{(3 \log(n)\log(n) + 55 \log(n^{10}) + 8 \log n) \cdot \log n}{\log(n)}=\infty.$$

You can derive the $O$ bounds and $\Omega$ bounds from the $\Theta$ bounds. I may have misplaced a few terms or two when typesetting; in which case, please point out.

$\endgroup$
1
  • $\begingroup$ If you are a purist and don't allow notations like $f(n)=O(g(n))$, replace the "=" with "is." $\endgroup$ May 14, 2019 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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