Runtime Analysis, Coefficients in logarithms? Ignorable?

115 Views Asked by At

I had a question regarding when we can ignore constants during Big O analysis. If I had $f(n)=\log5x$ and $g(n)=\log100x$, would the constants $5$ and $100$ be ignorable when considering $n \to \infty$, such that $f(n) = \theta(g(n))$? Conceptually, when is it acceptable to ignore constants when doing Big O analysis? (Dropping constants when they are simply added or multiplied as $n+100$ or $5n+20$ makes sense, but when constants mix with logs, exponents and bases I don't understand it as clearly). Thanks!

1

There are 1 best solutions below

3
On BEST ANSWER

The laws of logs tell you that $\log (5x)=\log(5)+\log(x)$ and so the constant in the logarithm can be thought of as one tacked on at the end.

Similarly if you have $e^{c+x}$ as your run time then as $e^{c+x}=e^x\cdot e^c$ this acts like multiplying on the outside which you also say is fine.

As per the comments, it is NOT ok if you have $e^{cx}, (c>1)$ as you can show that there is no constant $K$ such that eventually $Ke^x>e^{cx}$.