"$O$" notation in Stirling approximation

Question

In the Stirling approximation the formula as typically used in applications is $$\ln n! = n\ln n - n +O(\ln(n))$$ I'm confused about the last term "$O$" . What does it mean actually, and when do we apply it in a equation?

Answer 1

When the sequence $a_n$ converges to some finite $a$ as $n\to \infty$, we can approximate $a_n$ with $a$ for $n$ large enough. However, when $a_n$ diverges to infinity, such approximation cannot be done. Instead, we can look for the order of such divergence, i.e. how fast does $a_n$ grow. In your case about $$ a_n:= \ln n!-n\ln n+n $$ it is said that $a_n = O(\ln n)$. It means, that $a_n$ grows similar to the logarithm function. More precise description is given by this link.

Updated:

As did has mentioned, or as you can read in Clive's answer, from the definition of $O$ it only follows that $|a_n|$ is bounded from above by $c\cdot \ln n$ for some constant $c$. The precise rate of growth of $a_n$ is given by $\Theta(\cdot)$ which is also defined in the Wikipedia article I cited.

Answer 2

It means that $\ln n! = n\ln n - n + f(n)$ for some function $f$ which is asymptotically bounded by $\ln n$, in the sense that there is a constant $c$ and a number $n_0$ such that $|f(n)| \le c\ln n$ for all $n \ge n_0$.

Answer 3

In this specific context I recon the best understanding would be the following:

Imagine that in addition to the three terms above you have $k \in \mathbb{Z}^{+}$ more asymptotically smaller terms, e.g. $\log n + \log \log n + \log \log \log n+\ldots$. They are dominated by the asymptotically largest term here, i.e.:

$$ R(n) = \log n + \log \log n +\log \log \log n + \ldots \leq k \log n \\ \Leftrightarrow \lim_{n \to \infty}\frac{R(n)}{\log n}=k $$

In this case we use the big-O notation that $R(n)=O(\log n)$

By the way $-O(\log n)=+O(\log n)$, for details see the last chapter in Concrete Mathematics (1995) by Graham, Knuth and Patashnik