Big O notations and bounded function

120 Views Asked by At

In my exercise I have a function $f(n)$, of which they tell me that it is $O(1)$ when $n$ tends to $\infty$. The first thing I don't understand is this data. It happens that the exercise was changed, since the old hypothesis was that $ f (n) $ was bounded. For the truth to be bounded is stronger than being $ O (1) $ in a neighborhood of infinity (which is only to be bounded eventually). I would like to know if I am understanding this correctly.

On the other hand, the order of my exercise is to test for equality:

$$ [f (n) + O (n^{-1})] [1 + O (n^{-1})] = f (n) [1 + O (n^{-1})] $$

Making the product on the left side, it is enough to prove in definite (I hope so) that there exists $ M> 0 $ such that:

$$ | g (n) + h (n) / f (n) + h (n) g (n) / f (n) | \leq M / n $$ for $ n $ large enough. I don't know how to prove this happens though. In fact, I am skeptical that $ f (n) $ can be very small when $ n $ is large, in which case those ratios would be very large. Any help is welcome

1

There are 1 best solutions below

4
On BEST ANSWER

Let's start with that $f\in O(1),n\to\infty,n\in\mathbb{N}$ is equivalent to $f$ bounded. Last is not stronger, because, if $f$ is, as you wrote, "bounded eventually", then it will be also bounded. Let's prove it for non negative case: $f\in O(1)\Rightarrow \exists C>0,\exists N \in\mathbb{N}, f(n)\leqslant C$, where $n>N$. Let's choose maximum in numbers $A=\max \{f(1), \cdots, f(N)\}$, then $f(n)\leqslant \max (C,A),\forall n \in \mathbb{N}$. So, $f$ is bounded.

Then, as far as I can see, your doubt is fair, because for $f(n)=\frac{1}{a^n}$, where $a>1$ inequality $| g (n) + h (n) / f (n) + h (n) g (n) / f (n) | \leq M / n$ , where $g,h \in O\left(\frac{1}{n}\right)$, in general, will be false.