# Prove $n\log n\neq O(g(n))$ where $g(n)$ alternates between $\log^*n$ and $n!$

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?

• Do you mean $f(n) \neq O(g(n))$? Apr 16 at 11:34
• Yes, exactly thank you Apr 16 at 11:37
• 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?
– roro
Apr 16 at 11:43

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

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

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.