Proving whether $1.117 * n^2 * \sqrt{n} \in O(\log \log n)$ is valid

Question

For starters both functions, $1.117 * n^2 * \sqrt{n}$ and $\log \log n$ for $n > 0$, increase monotonically with $n$.

Answer 1

In going from the 3rd last line to the 2nd last line, you make an erroneous transformation. You originally had $K$ as an exponent which the rest of the expression was raised, but unjustifiably change it so that $K$ is merely multiplied by the rest of the expression. This mistake scuttles the proof.

You will find, in fact, that the statement you are trying to prove here is not true; dividing through by $n$, it's equivalent to asking whether $n^{0.117} \in O(\log n)$, which false (note that $\log n^{0.117} = 0.117 \log n$, and so, up to constant factors, we have that $\log n$ is merely logarithmic as a function of $n^{0.117}$).

Answer 2

The claim is wrong. We can try to prove $n^{1.004} \in \Omega(n\log n)$. $$ n^{1.004} \geq C\ n \log n \Leftrightarrow \\ n^{\frac{1}{250}} \geq C \log n $$ Now I arbitrarily set $C := 1$ and we will try to find $n_0$ such that $\forall n \geq n_0$, the inequality is respected : $n^{\frac{1}{250}} \geq \log n $. I also define $n = e^x$ for some $x > 0$. ( We assume $n$ to be "large" so this is always possible)

\begin{align} n^{\frac{1}{250}} &\geq \log n & \Leftrightarrow \\ e^{\frac{x}{250}} &\geq x & \Leftrightarrow\\ \sum_{i=0}^\infty \frac{(\frac{x}{250})^i}{i!} &\geq x & \overset{(*)}{\Leftarrow} \\ \frac{(\frac{x}{250})^2}{2!} &\geq x & \Leftrightarrow \\ \frac{x^2}{2\cdot 250^2} & \geq x & \Leftrightarrow \\ x &\geq 2\cdot 250^2 & \Leftrightarrow \\ e^x &\geq e^{2\cdot 250^2} & \Leftrightarrow \\ n & \geq e^{2\cdot 250^2} \end{align} $(*)$ The sum contains only positive terms. We keep only the one when $i=2$.

Hence when $n \geq e^{2\cdot 250^2}$ we have that $n^{1.004} \geq n \log n$