0
$\begingroup$

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...

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

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<c_1\leq (\frac{3}{\log^{7}(n) } + \frac{558}{\log^8(n)}), \ \forall n \geq n_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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The $loga^b = b*log a$ trick did it! Clear explanation - Thanks! $\endgroup$ – Alex5207 May 17 at 12:53
  • $\begingroup$ btw try using $\log$ not $log$ .. just add a backslash ;) and no need for an asterisk for multiplication .. good luck $\endgroup$ – Ahmad Bazzi May 17 at 12:54
  • $\begingroup$ Thanks - Got it :-) $\endgroup$ – Alex5207 May 17 at 12:55
0
$\begingroup$

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$

|cite|improve this answer
$\endgroup$

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.