# What does $\tilde{O}_P(N^\alpha)$ mean?

What does $$\tilde{O}_P(N^\alpha)$$ mean? It appears in an estimation error mention in this paper, in the second paragraph on page 3.

What does big O subscript P mean in a probability context?

Pulled from: http://www2.math.uu.se/~svante/papers/sjN6.pdf (definition D5).

A probabilistic version of $$\mathcal{O}$$ that is frequently used is the following:

$$X_n = O_\text{P}(\alpha_n)$$ if for every $$\epsilon > 0$$ there exists constants $$C_{\epsilon}$$ and $$n_{\epsilon}$$ such that $$\mathbb{P}(|X_n| \leq C_{\epsilon}\alpha_n) > 1 − \epsilon$$ for every $$n \geq n_{\epsilon}$$. In other words, $$X_n/\alpha_n$$ is bounded, up to an exceptional event of arbitrarily small (but fixed) positive probability. This is also known as $$X_n/\alpha_n$$ being bounded in probability.

So combining this and D.W.'s answer we get:

$$X_n \in \tilde{O}_{\text{P}}(\alpha_n)$$ means for every $$\epsilon > 0$$ there exists constants $$C_\epsilon$$ and $$n_{\epsilon}$$ such that $$\mathbb{P}(|X_n| \leq C_{\epsilon}\alpha_n n^{\gamma}) > 1 - \epsilon$$ for every $$n \geq n_{\epsilon}$$ and for all $$\gamma > 0$$.

An looser terms $$X_n \in \tilde{O}_{\text{P}}(\alpha_n)$$ means $$X_n$$ is bounded by $$\alpha_n$$ within a polynomial factor with high probability.

• I think this is a clear and correct answer, thanks!
– luw
Apr 27, 2019 at 22:29
• @luw cool, I also combined this info with $\tilde{O}$ from D.W.'s answer to make it more complete.
– ryan
Apr 27, 2019 at 22:34

It depends on context; often, saying $$f(n) \in \tilde{O}(g(n))$$ means $$f(n) \in O(g(n) n^{\epsilon})$$ for all $$\epsilon>0$$. For example, $$n^2 \log n \in \tilde{O}(n^2)$$.

• Any idea what the subscript $P$ could mean? Apr 27, 2019 at 17:50
• @Discretelizard, no clue.
– D.W.
Apr 27, 2019 at 18:13
• @Discretelizard could it possibly mean Polynomial? Then you have $f(n) \in \tilde{O}_P(g(n))$ means $f(n) \in O(g(n) \cdot \text{poly}(n))$ ?
– ryan
Apr 27, 2019 at 19:30
• @ryan I doubt it, just the tilde is already widely used to ignore polynomial factors. Judging from the context in the paper, I suspect it has something to do with probability. Apr 27, 2019 at 19:34