0

Say we have the following: $$f(x) = \log(x)$$ $$g(x)= \log(20x)$$

If we want to compare the two using big O notation, does this mean that I have to keep the factor $20$ so that I can conclude that $f(x) = O(g(x))$? I'm a little confused since when reading on evaluating big $O$, the general thing is to remove the multiplicative factors. Thanks!

Arnaud D.
  • 20,884
O_O
  • 129
  • " Keep the factor $20$ ? " What does it mean ? Where should it go ? – Atmos Jan 11 '18 at 22:05
  • I mean keep the factor 20 when comparing the two functions in big O notation. – O_O Jan 11 '18 at 22:08
  • Yes you compare two functions. One is $\displaystyle x \mapsto \ln(x)$ and the other is $\displaystyle x \mapsto \ln(20 x)$. – Atmos Jan 11 '18 at 22:11
  • To abuse notation, $O(\log(20x)) = O(\log(x))$. Being able to ignore factors like this is, really, the entire point of big O notation. – Duncan Ramage Jan 11 '18 at 22:14
  • If we consider the two functions to have the same big O notation (O(log(x)), we wouldn't be able to do a good comparison of the two functions though, right? But I guess on the big picture, they do both behave similarly. I need to get more familiar with this relative notion. Thanks for the feedback. – O_O Jan 11 '18 at 22:24
  • They behave the same since $\log(20x)-\log(x)=\log(20)=\operatorname{const}$ – kingW3 Jan 12 '18 at 16:44

1 Answers1

2

$$lim_{x\to\infty}\frac{f(x)}{g(x)}=lim_{x\to\infty}\frac{\log x}{\log 20x}=lim_{x\to\infty}\frac{\log x}{\log 20 +\log x}=1\ne0\to f(x)=O(g(x))$$

Mostafa Ayaz
  • 31,924