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

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Is $\log^2 n$ supposed to mean $(\log n)^2$ or $\log \log n$? $\endgroup$ – dkaeae May 14 at 11:25
  • $\begingroup$ Yes it is @dkaeae $\endgroup$ – Boris Grunwald May 14 at 11:43
  • $\begingroup$ @BorisGrunwald $(\log n)^2$ and $\log \log n$ are not the same thing. $\endgroup$ – dkaeae May 14 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$ – BearAqua May 14 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$ – BearAqua May 14 at 12:48
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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ In my computation, I assumed that $\log^k n$ means $(\log(n))^k$. $\endgroup$ – Juho May 14 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.

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

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.