-2
$\begingroup$

I have to prove that $f(n) \neq O(g(n))$, where $f(n) = n\log n$ and $g(n)$ is $\log^*n$ if $n$ is odd and $n!$ if even.

So my thought is to say that $f(n) = O(g(n))$ and then with the definition prove that this is wrong, but i am struggling. Can someone help me?

$\endgroup$
3
  • 1
    $\begingroup$ Do you mean $f(n) \neq O(g(n))$? $\endgroup$
    – Russel
    Apr 16 at 11:34
  • $\begingroup$ Yes, exactly thank you $\endgroup$
    – gianluigi
    Apr 16 at 11:37
  • $\begingroup$ I am not sure if this is the way to go, but maybe someone with higher knowledge can give me a double check: Assume $f(n) = O(g(n))$. Then: \begin{equation*} g(n) = \Omega (f(n)) \Rightarrow f(n) = o(g(n)) \Leftrightarrow \lim_n \frac{f(n)}{g(n)} = 0. \end{equation*} Can you prove this is a contradiction? $\endgroup$
    – roro
    Apr 16 at 11:43

2 Answers 2

2
$\begingroup$

There is no constant such that $n\log n<c\log n$ for all odd $n$. (Obviously, there is no constant such that $n<c$ for all odd $n$).

$\endgroup$
4
  • $\begingroup$ It is not logn, it is log*n $\endgroup$
    – gianluigi
    Apr 16 at 14:12
  • 1
    $\begingroup$ $\log^*(n) \leqslant \log n$, so the argument still holds. $\endgroup$
    – Nathaniel
    Apr 16 at 14:16
  • $\begingroup$ Yes I didn’t assume that you are wrong. It’s was my fault $\endgroup$
    – gianluigi
    Apr 16 at 14:20
  • 1
    $\begingroup$ @gianluigi: see Nathaniel's comment. $log^*$ grows even slower. $\endgroup$ Apr 16 at 14:21
0
$\begingroup$

Let me suggest formal approach to question, because, of course, inequalities are important, but also are important conditions on variables in this inequalities.

To prove directly, that some function is not in some big-$O$, you need negation of definition $f(n)\in O(g(n)),n\to\infty$:

formal defintion is $$\exists c >0, \exists n_0\in\mathbb{N}, \forall n>n_0, f(n)\leqslant c\cdot g(n) $$ so, negation, $f(n)\notin O(g(n)),n\to\infty$, will be

$$\forall c >0, \forall n_0\in\mathbb{N}, \exists n>n_0, f(n)>c\cdot g(n) $$ In definition $n$ is variable and $c,n_0$ are constants which we want to find.

In negation $c, n_0$ are variables and we want to determine $n=n(c, n_0)$ subsequence of $\mathbb{N}$.

So, in given case, to prove, that $n \log n \notin O(g(n))$, we need prove, that $n \log > g(n)$ in conditions done above. Using nice idea from adjacent answer, we can consider two cases:

in case of odd $n$, for $\forall c >0, \forall n_0\in\mathbb{N}$ let's consider $n \log n > c \log n \geqslant c \log^* n$. To fulfill this inequality is enough to take $n=\max (n_0, \lfloor c \rfloor +1)$.

even case can be done in similar way.

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