Does there exist $f$ such that $f(n)=\Omega(\log n)$ and $(f(n))^2=O(f(n))$?

157 Views Asked by At

I have to prove/disprove the next 2 statements. I've succeeded with the second, not with the first.

  1. There exists $f$ such that $f(n)=\Omega(\log n)$ and $(f(n))^2=O(f(n))$.

  2. If $f$ and $g$ are monotonically increasing functions, such that $ f(g(n)) = O(n) $ and $f(n)=\Omega(n)$ then $g(n)=O(n)$.

1

There are 1 best solutions below

6
On

Hint: If $f(n)^2 \le K |f(n)|$ and $f(n) \ne 0$, then $|f(n)| \ldots$