Results 1 to 4 of 4

Thread: O(7^f(n)) and 3^(O(f(n))

  1. #1
    Junior Member
    Joined
    Jan 2013
    From
    Croatia
    Posts
    49
    Thanks
    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,316
    Thanks
    1284

    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} $
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2013
    From
    Croatia
    Posts
    49
    Thanks
    1

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

    Ok I get that, but still can't solve it
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,316
    Thanks
    1284

    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)$.
    Last edited by SlipEternal; Apr 16th 2018 at 07:07 AM.
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum