Exponential vs Polynomial running time

Question

As per this article: https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time we know that exponential is worse than polynomial in terms of running time. Is it safe to say that any powers for the exponential and polynomial would still lead to exponential being worse? e.g. if I have f(n) = n^0.75 vs g(n) 3^log2(n/2), can I assume that f(n) = O(g(n))?

Answer 1

Firstly, if your size parameter is $\log_2(n)$--which must be the same for both expressions for consistency--then polynomial complexity would be $$f(n)=\log_2(n)^{0.75}$$ and exponential complexity would be $$g(n)=3^{\log_2(n/2)}=3^{\log_2(n)-1}=O(3^{\log_2(n)})$$ whereby clearly your $g(n)$ grows much faster than your $f(n).$ Taking any constant powers of the two will not change this either.

Answer 2

Yes. Think about this in terms of evaluating the limit of the exponential over the polynomial. The point of intersection will vary, but the rate of growth of the exponential will always be larger than the polynomial after a certain point.

In a more mathematically rigorous sense, think about this as applying L'Hôpital's rule. You will see that the derivative of the exponential will always be larger than that of the polynomial after a certain point.