# “$O$” notation in Stirling approximation

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?

-

## migrated from physics.stackexchange.comJan 3 '13 at 20:40

This question came from our site for active researchers, academics and students of physics.

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$.

-
You don't need the $n_0$, do you? – xavierm02 Jan 3 '13 at 23:35
@xavierm02: What do you mean? You could stick the words 'eventually' or 'sufficiently large' in there somewhere, but the $n_0$ will always be there implicitly. (And when you decode what 'eventually' or 'sufficiently large' mean mathematically, the $n_0$ will show its face once again.) – Clive Newstead Jan 3 '13 at 23:38
Never mind. I though that for $f(n)=O(g(n))$, we could take $n_0=0$ or $n_0 =1$ but $g(0)$ and $g(1)$ don't need to be defined... But if $g(n)$ were defined and non null $\forall n$, you could take $n_0'=0$ and $C' = \max \left\{\cfrac{|f(n)|}{|g(n)|}, n < n_0\right\} \cup \{C\}$ – xavierm02 Jan 4 '13 at 0:05
@xavierm02 As you say, roughly speaking, $n_0$ is very much needed when $g(n)$ starts by being zero. – Did Jan 4 '13 at 8:33

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.

-
grows similar to the logarithm function... No. – Did Jan 3 '13 at 20:52
$0$ is $O(\ln n)$... – xavierm02 Jan 3 '13 at 23:33
@did: I didn't pretend to make a precise statement there, which is anyway impossible with the word "similar" - that's why I referred OP to the explicit definition of $O$. I rather meant, that $O$ is often used to show the order of the growth, e.g. in the results on the complexity of algorithms. Nevertheless, let me avoid a possible misreading – Ilya Jan 4 '13 at 7:33
@xavierm02 Indeed. :-) – Did Jan 4 '13 at 8:30

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

-
I do not understand the $\iff$. – Did Jan 4 '13 at 8:31