1

This question might be very simple, but I'm having a hard time understanding it.

Suppose $$f(n) = \frac{O(n)}{1+O(1/n^2)}.$$

How can I "simplify" the fraction so that I get $f(n) = O($something$)$?

I think it should be $f(n) = O(n)$ ...

My problem is that when I see $O(1/n^2)$ in the denominator, I can only say something about an upper bound (whereas I would like a lower bound, I think). For me it would make more sense to "simplify" $f$ if in the denominator was instead $1 + \Omega(1/n^2)$. Or is it the same?

A different question would be if $f(n) = \frac{O(n)}{O(1/n^2)}$. Notice that $\frac{O(g(n))}{O(h(n))} \neq O\left(\frac{g(n)}{h(n)}\right)$.

Babado
  • 1,306
  • There exist positive constants $c_i$, $i=1,2$, such that for sufficiently large $n$, $$ \left| {f(n)} \right| \le \frac{{c_1 n}}{{1 - \frac{{c_2 }}{{n^2 }}}} \le 2c_1 n. $$ Note that $g(n)=O(h(n))$ means $|g(n)|\leq c|h(n)|$ with a suitable $c>0$ and sufficiently large $n$. – Gary Mar 28 '21 at 12:24
  • Ohhh ok @Gary, thanks for that explanation. I was missing that reasoning somehow. – Babado Mar 28 '21 at 13:04
  • Just let me ask you one more thing, if $f(n) = \frac{O(n)}{O(1/n^2)}$, can I write $f(n) = O(n^3)$? I think in this case I would need to have $f(n) = \frac{O(n)}{\Omega(1/n^2)}$... – Babado Mar 28 '21 at 13:28
  • 1
    You are correct, e.g., $$ g(n) = n=O(n),; h(n) = \frac{1}{{n^3 }} = O!\left( {\frac{1}{{n^2 }}} \right) \Rightarrow O(n^3 ) \ne n^4 = \frac{{g(n)}}{{h(n)}} = \frac{{O(n)}}{{O!\left( {\frac{1}{{n^2 }}} \right)}}. $$ – Gary Mar 28 '21 at 13:30

1 Answers1

1

We can do a series expansion and obtain \begin{align*} \color{blue}{f(n)} &= \frac{\mathcal{O}(n)}{1+\mathcal{O}\left(\frac{1}{n^2}\right)}\\ &=\mathcal{O}(n)\left(1+\mathcal{O}\left(\frac{1}{n^2}\right) +\mathcal{O}\left(\frac{1}{n^4}\right)+\mathcal{O}\left(\frac{1}{n^6}\right)+\cdots\right)\tag{1}\\ &=\mathcal{O}(n)\left(1+\mathcal{O}\left(\frac{1}{n^2}\right) +\mathcal{O}\left(\frac{1}{n^2}\right)+\mathcal{O}\left(\frac{1}{n^2}\right)+\cdots\right)\tag{2}\\ &=\mathcal{O}(n)\left(1+\mathcal{O}\left(\frac{1}{n^2}\right)\right)\tag{3}\\ &=\mathcal{O}(n)+\mathcal{O}\left(\frac{1}{n}\right)\tag{4}\\ &\,\,\color{blue}{=\mathcal{O}(n)}\tag{5} \end{align*}

Comment:

  • In (1) we consider functions $f:\mathbb{N}\to\mathbb{C}$ with $f(n)=\mathcal{O}\left(\frac{1}{n^2}\right)$ and do a geometric series expansion \begin{align*} \frac{1}{1+f(n)}=1-f(n)+\left(f(n)\right)^2-\left(f(n)\right)^3+\cdots\qquad\qquad |f(n)|<1 \tag{6} \end{align*} Since Big-Oh means something that is in absolute value less than a constant number times we have that both $f(n)=\mathcal{O}\left(\frac{1}{n^2}\right)$ and $-f(n)=\mathcal{O}\left(\frac{1}{n^2}\right)$ and we can use the representation (1). Note that contrary to (6) the $=$ symbol in (1) does not mean equality, but is contained (left-to-right) instead, as usual when Big-Oh comes into play.

  • In (2) we use $\mathcal{O}\left(\frac{1}{n^\alpha}\right)=\mathcal{O}\left(\frac{1}{n^2}\right)$ if $\alpha\geq 2$.

  • In (3) we use $\mathcal{O}\left(\frac{1}{n^2}\right)+\mathcal{O}\left(\frac{1}{n^2}\right)=\mathcal{O}\left(\frac{1}{n^2}\right)$.

  • In (4) we use $\mathcal{O}(f)\mathcal{O}(g)=\mathcal{O}(fg)$.

  • In (5) we use $\mathcal{O}\left(\frac{1}{n}\right)=\mathcal{O}(n)$.

Markus Scheuer
  • 108,315