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

Question

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?

Answer 1

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

Answer 2

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.