Why sup is needed for asymptotic notation definition?

115 Views Asked by At

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.

1

There are 1 best solutions below

1
On

$\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)|}$