0

I saw in a book that $\ f(n) = O(g(n)) $ iff $\lim_{n\to \infty} \sup \left|\frac{f(n)}{g(n)}\right| <\infty$

my question is: Why sup is needed?

The way I understand it, the fraction of two different functions with the same growth rate (for example $\ n^2 $ and $\ 3n^2 $ ) will always be a constant.

Bernard
  • 175,478
joe markovic
  • 21

1 Answers1

0

$\limsup \alpha_{n}$ is the supremum of all subsequential limits. See, a sequence $(\alpha_{n})_{n\geq 1}$ need not be convergent and $\lim_{n} \alpha_{n}$ need not always exist.

Now, take all possible subsequences of $(\alpha_{n})_{n\geq 1}$. Then $$\limsup \alpha_{n}= \sup \{a\in\mathbb{R}: a=\lim_{k\rightarrow \infty} \alpha_{n_{k}},\; (\alpha_{n_{k}})_{k\geq 1}\; \text{is a subsequence of } \;(\alpha_{n})_{n\geq 1}\}.$$ An equivalent definition is $$\limsup \alpha_{n}=\inf_{n\geq 1}\sup_{k\geq n} \alpha_{n_{k}}$$.

Unlike the limit, the limit superior always exists.If the sequence $(\alpha_{n})_{n\geq 1}$ is bounded then it has a convergent subsequence (by Bolzano Weirestrass theorem) and we can find the real number that represents $\limsup \alpha_{n}$. If $(\alpha_{n})_{n\geq 1}$ is not bounded then we have $\limsup \alpha_{n}=+\infty$, and the limit superior exists in that sense.

Think of the sequences $(a_n)_{n\geq 1}=((-1)^n)_{n\geq 1}$ or $(b_n)_{n\geq 1}(\sin(n))_{n\geq 1}$. These sequences do not have a limit, but you can extract convergent subsequences from them. We can calculate $$\limsup_{n} a_{n}=1$$ and $$\limsup_{n} b_{n}=1$$.

In your question, we do not know if $\lim \frac{|f(n)|}{|g(n)|}$

Medo
  • 3,070
  • 12
  • 28
  • Again back to the definition in your question. $f(n)=O(g(n))$ when $n\rightarrow \infty $ if there is a $C>0$ such that $$|f(n)/g(n)|\leq C$$ for all $n$ big enough. This equivalent to the sequence $(|f(n)/g(n)|){n\geq 1}$ is bounded. So it has convergent subsequences, and we find $\limsup{n\rightarrow \infty} |f(n)/g(n)|<\infty$ . – Medo Mar 12 '18 at 01:56