2
$\begingroup$

Given the functions $f$, $g$: $\mathbb{N} \to \mathbb{R}$

I have to prove that,

$f \in O(g)$, iff \limsup_{n\to\infty}|\frac{f(n)}{g(n)}| < \infty

How can I prove it formally (at best using the O-Notation definitions)? Sorry to pose the question quite straightforward without describing what I already tried and where I got stuck. In this case, I just have no clue where to start from.

Maybe a hint of anything to start with should suffice.

Thanks!

  • 0
    Write the definition of $O$, then one direction is easy.2012-04-24

1 Answers 1

1

Let's write the definition of $f \in O(g(n))$ and \lim\sup_{n\rightarrow\infty}|\frac{f(n)}{g(n)}|<\infty. We get

\begin{align} (1)& \lim_{n\rightarrow\infty}\left(\sup\left\{\left|\frac{f(k)}{g(k)}\right| : k \ge n\right\}\right) < \infty \\ (2)& \ f(n)\in O(g(n)) :\Longleftrightarrow \text{$\exists N,K>0$ $\forall n\ge N\colon\ |f(n)| \le K\ |g(n)|$.} \end{align}

We define Let $S_n := \sup\left\{ \left|\frac{f(k)}{gk)}\right|: k\ge n\right\}$.

(1)$\Rightarrow$(2): Let $a$ be the limit to which the sequence in (1) converges. By definition of the limit we have that $\forall \varepsilon > 0\ \exists N\ \forall n\ge N\colon | S_n - a | \le \varepsilon.$ Fix any $\varepsilon>0$ and set $K=\varepsilon+a$. The above implies that there exists an $N>0$ such that |f(n)| < (\varepsilon+a)|g(n)| for all $n\ge N$, which matches the right hand side of (2).

(2)$\Rightarrow$(1): Starting from the right hand side of (2), we immediately see that $S_N \le K$ and in fact $S_n \le K$, for any $n \ge N$. We observe that $(S_n)_{(n\ge N)}$ is an increasing sequence that is bounded from above by $K$. Thus $\lim_{n\rightarrow\infty}S_n$ is converging, which shows (1).