1. ## O(7^f(n)) and 3^(O(f(n))

I need help with prooving or disaprooving relations between $\mathcal{O}(7^{f(n)})$ and $3^{\mathcal{O}(f(n))}$, where $f$ is function from natural to positive real numbers. I need to find example for inclusion which is not true and to prove the one that is true.Thanks

2. ## Re: O(7^f(n)) and 3^(O(f(n))

$f (n)=1$

$7^1=3^{1 (\ln 7/ \ln 3 )}$

The constant on the left is 1 and the right is obviously $\dfrac{\ln 7}{\ln 3}$

3. ## Re: O(7^f(n)) and 3^(O(f(n))

Ok I get that, but still can't solve it

4. ## Re: O(7^f(n)) and 3^(O(f(n))

You asked for an example where they are equal. That is an example. I gave explicit coefficients that make them equal. Now, you just need a function where no such coefficient exists. You need a function where there does not exist $\alpha,\beta \in \mathbb{R}$ such that:
$\displaystyle \alpha 7^{f(n)} = 3^{\beta f(n)}$

I've never formally worked on big O notation, but that was my general understanding of it. Let's take the log of both sides:

But, if $\alpha = 1$ and $\beta = \dfrac{\ln 7}{\ln 3}$, then you get equality on both sides. So, I think it is true for any $f(n)$.

Edit: I'm mistaken. You need to fix $\alpha$ and show that there exists $\beta$ that makes this true. So, let's solve for $\beta$:

$\displaystyle \alpha 7^{f(n)} = 3^{\beta f(n)}$

$\displaystyle \ln \alpha + f(n)\ln 7 = \beta f(n) \ln 3$

$\displaystyle f(n)(\beta \ln 3 - \ln 7) = \ln \alpha$

So, you only have equality when $\alpha = 1, \beta = \dfrac{\ln 7}{\ln 3}$ or $f(n) = c$ for some constant $c\in \mathbb{R}$.

This implies it should be false for any nonconstant function $f(n)$.