About the $O$ notation with a subscript

Question

The usual $O$ notation was that $f(x) = O(g(x))$ meant that there exists a positive real number $C$ such that $|f(x)| \le C g(x)$ for sufficiently large $x$. However I came across the notation $O_r(\log x)$, where $r$ was a natural number. Having a subscript, what does it mean? I have tried to find if there is an explanation of this in the Wikipedia page about the Big $O$ notation but there was no such explanation. Would you please help me understand what $O_r(\log x)$ means?

Answer 1

I can make no promises without a source for this notation, but I most frequently see this notation to mean the constant $C$ guaranteed by the big oh is allowed to depend on $r$. It can be useful to keep track of this to ensure you don't accidentally have two constants which depend on each other!

For a concrete example, in a power series expansion about the point $z_0$, we might have (when $|z-z_0| < r$):

$$f(z) = \sum_{k=0}^n a_k (z-z_0)^k + O_{n,r}(|z|^{n+1})$$

This means the constant depends both the degree of the approximation and the desired radius of approximation (which, of course, must be less than the radius of convergence).

For a more detailed explanation of this notation, see the second PDF at this link. It is a set of notes on asymptotic notation by A.J. Hildebrand, which I have always found extremely well written and useful.

Edit: For convenience, here is an example given in the linked notes. I have copied it almost verbatim.

For any $0 < r < 1$, we have

$$\log (1+z) = O_r(|z|)~~~~~~(|z| < r)$$

Notice, for $|z| < 1$, we have:

$$\log(1+z) = \sum_{n=1}^\infty \frac{(-1)^{n+1}}{n} z^n$$

Thus, we have

$$ |\log(1+z)| \leq \sum_{n=1}^\infty \frac{1}{n}|z^n| \leq \sum_{n=1}^\infty |z|^n = \frac{1}{1-|z|}|z| $$

Now if we restrict to $|z|<r$, we can get a constant which does not depend on $|z|$, and thus is suitable for Big-oh:

$$\frac{1}{1-|z|}|z| \leq (1-r)^{-1} |z|$$

Thus we see that the constant in the Big-oh depends on $r$.

---

I hope this helps ^_^