0

Intuitively I know that $ 5^{xf(x)} \in \mathcal O (5^{f(x)}) $ but how would I go about proving this? I am at my wit's end on this.

$ 5^{xf(x)} \in \mathcal O (5^{f(x)}) \Leftrightarrow \exists c, B \in \mathbb{R}^+, \forall n \in \mathbb{N}, n \geq B \Rightarrow 5^{xf(x)} \leq c * 5^{f(x)} $

Is it really necessary to pin down a specific $ c $ and $ B $? How would I go about acquiring a general solution for this?

Thanks.

tuba09
  • 323
  • 1
    This isn't necessarily true. For example $f(x)=x$ (assuming you're using big-oh notation). –  May 31 '14 at 03:22
  • It's not even true for their exponents: $xf(x)$ is a larger growth class than $f(x)$ by more than any constant, i.e. $f(x)=o(xf(x))$. Exponentiating $f(x)$ and $xf(x)$ can only make the gap between their growth levels even more pronounced. – anon May 31 '14 at 03:47
  • 2
    I found $f \equiv 1$ to be a nice counterexample. – PhoemueX May 31 '14 at 08:07
  • Thanks PhoemueX, how would I finagle the inequality to make the counter-example work? – tuba09 May 31 '14 at 13:52

1 Answers1

2

$$ \frac{5^{x f(x)}}{5^{f(x)}} = 5^{(x-1)f(x)} $$

This probably goes to infinity, which implies

$$ 5^{x f(x)} = \omega(5^{f(x)})$$

although if your $f$ was chosen so that the limit goes to $0$, it would be little-oh. Or if the limit went to a finite number, it would be $\Theta$