# Running time correct with Omega?

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

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

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.

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

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.

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