# Time complexity for an algorithm

How do you realize that $$(3log^2(n) + 55log(n^{10})+8log(n))*log(n) \neq \Omega(log^{10}(n))$$ ,where $$log^x(n)$$ means $$(log(n))^x$$

I know that by definition, if $$f(n) = \Omega(g(n))$$ then there exists a constant $$c_1$$ such that $$0 \leq c_1 *g(n) \leq f(n)$$ for all $$n > n_0$$. In our case it yields $$c_1*log^{10}(n) \leq (3log^2(n) + 55log(n^{10})+8log(n))*log(n)$$

$$\Rightarrow$$

$$c_1 \leq \frac{3log^3(n)}{log^{10}(n)} + \frac{55log(n^{10})*log(n)}{log^{10}(n)} + \frac{8log^{2}(n)}{log^{10}(n)}$$

RHS: It's fairly easy to see that the denominator is larger than the nominator of both the first and third term, which means that $$55log(n^{10})*log(n) > log^{10}(n) + c_1$$ for some $$n_0$$ if the first equation holds.

I am just not able to see how to manipulate the equation to realize it...

• you should mention that there exists $c_1 > 0$ and $n_0 > 1$ such your inequality holds for all $n > n_0$. – Ahmad Bazzi May 17 at 10:22
• Good point, thx – Alex5207 May 17 at 10:24

I'll take it from where you paused. Assume your claim is true, that is the following is correct $$(3\log^2(n) + 55\log(n^{10})+8\log(n))\log(n) \neq \Omega(\log^{10}(n))$$ Then there exists $$c_1 > 0$$ and $$n_0 > 1$$ such that for all $$n > n_0$$,we have $$c_1\log^{10}(n) \leq (3\log^2(n) + 55\log(n^{10})+8\log(n))\log(n)$$ Divide both sides by $$\log(n)$$ $$c_1\log^{9}(n) \leq (3\log^2(n) + 55\log(n^{10})+8\log(n))$$ Use $$\log a^b = b \log a$$ $$c_1\log^{9}(n) \leq (3\log^2(n) + 550\log(n)+8\log(n))$$ Divide again by $$\log (n)$$ $$c_1\log^{8}(n) \leq (3\log(n) + 558) \tag{1}$$ Your task now is to find me a $$c_1 > 0$$ and $$n_0 > 1$$, such that for all $$n > n_0$$ such that $$(1)$$ is true. Written differently, $$\exists n_0 > 1 \quad \mid \quad 0 The above is clearly not true. The larger $$n$$ is, the upper bound goes to zero. By the sandwich theorem, you get that $$c_1$$ has to be zero. By contradiction, the initial hypothesis is false.
• The $loga^b = b*log a$ trick did it! Clear explanation - Thanks! – Alex5207 May 17 at 12:53
• btw try using $\log$ not $log$ .. just add a backslash ;) and no need for an asterisk for multiplication .. good luck – Ahmad Bazzi May 17 at 12:54
Let us denote $$y = \log n$$, then our inequality transforms to $$c_1 \leq \frac{3}{y^7} + \frac{550}{y^8} + \frac{8}{y^8}$$
and we need to prove that for any $$c_1 > 0$$ this inequality is violated for arbitrary large $$y$$.
Let us take any $$y > \max(1, \frac{550 + 8 + 3}{c_1})$$. Then we have $$\frac{3}{y^7} + \frac{550}{y^8} + \frac{8}{y^8} < \frac{550 + 8 + 3}{y} < \frac{550 + 8 + 3}{\frac{550 + 8 + 3}{c_1}} = c_1$$