Big-O Notation and Algebra

1k Views Asked by At

This is my first question here. Trying to simplify the following.

$$f = O\left(\frac{5}{x}\right) + O\left(\frac{\ln(x^2)}{4x}\right)$$

I give it a try as follows.

$$\begin{align} f &= O\left(\frac{5}{x}\right) + O\left(\frac{2\ln(x)}{4x}\right), \\ f &= O\left(\frac{5}{x}\right) + O\left(\frac{\ln(x)}{2x}\right), \\ f &= O\left(\frac{10}{2x}\right) + O\left(\frac{\ln(x)}{2x}\right), \\ f &= O\left(\frac{10 + \ln(x)}{2x}\right), \\ f &= O\left(\frac{\ln(x)}{2x}\right). \end{align}$$

Is this OK?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, that's ok.

Note that you can always omit non-zero multiplicative constants in $O(\cdot)$-terms. For instance, $O(4x) = O(x)$ and $O(2/x) = O(1/x)$. So you could get rid of those constants right away, and get a somewhat shorter version of the proof:

$$f = O\left(\frac{5}{x}\right) + O\left(\frac{\ln(x^2)}{4x}\right) = O\left(\frac{1}{x}\right) + O\left(\frac{\ln x}{x}\right) = O\left(\frac{\ln x}{x}\right).$$

But nothing is wrong with your derivation either.