Is it true that for some positive $g(n)$ then $h(n) = g(n)^{g(n)}, h(n) \notin O(g(n))$

30 Views Asked by At

I'm currently working on a homework and we are given a function $g(n) \geq \frac{1}{6}n^3$ and we are trying to give the tightest relation on $O(g)$ and $\Omega(g)$. We are also allowed to say that we don't have enough information on the function to determine this.

I've proven the first relation, meaning $O(g) \not\subset \Omega(g)$. As for $\Omega(g) \not\subset O(g)$, most of my class think we don't have enough information, but I've figured we could create a function based on $g(n)$ that grows faster than it. So I've defined $h(n) = g(n)^{g(n)}$ and the proof follows easily if $h(n)$ grows faster than $g(n)$, something I've not been able to prove yet, but I feel it's true since I've tried it with most common classes of functions that respect the condition above. Can someone point me in the right direction to prove it, or disprove it?

1

There are 1 best solutions below

0
On

I've found an answer: $\frac{g(n)^{g(n)}}{g(n)} = g(n)^{g(n)-1}$ which means that as long as $g(n)$ has no upper bound and is an increasing function, this works.