1

I want to prove the following:

  1. $\ln(f(n))\in \theta(\ln(g(n)))$
    It's true that: $$(g(n))^{f(n)}\in \theta((f(n)^{g(n)})$$


How I can use $\ln$ function to prove it? prove by definition is preferred? or with limit rule?

tinlyx
  • 1,534
Ofir Attia
  • 3,136

1 Answers1

0

It is not true. For example, let $f(n)=n$ and $g(n)=2n$. Then $f(n)^{g(n)}=n^{2n}=n^n n^n$ and $g(n)^{f(n)}=2^n n^n$. However, as $n\to\infty$, $\frac{2^nn^n}{n^nn^n}\to 0$.

Remark: The question could also be interpreted as asking whether the implication holds in the other direction. It does.

André Nicolas
  • 507,029