# What does $O(T^{-\eta})$ mean?

Let $\hat{\theta}$ be an estimator of a true parameter $\theta$. I am confused with the following (simplified) statement in a paper: $$\Pr(\lVert\hat{\theta} - \theta\rVert \leq \kappa) \geq 1 - O(T^{-\eta}),$$ where $\eta > 0$.

So how do I reed it? My guess is that as $T\to \infty$ we have that $T^{-\eta} \to 0$ and we should consider that $O(T^{-\eta})$ tends to zero. Then, I would read it as follows: as $T$ goes to infinity, the probability that difference between the estimator and the true parameter is less than any positive constant $\kappa$ goes to one.

Confusion arises also form the fact that I am not sure what $O(\cdot)$ means. Is it in terms of algorithm complexity or convergence of a sequence. So I mainly look for explanation of $O(T^{-\eta})$ term.

• @Tim, the paper is Barigozzi, M., & Brownlees, C. T. (2016). Nets: Network estimation for time series. The statement is taken from Proposition 2 page 16. Commented Oct 20, 2017 at 14:21
• @Tim, you picked draft version. You can find the correct one by the following link papers.ssrn.com/sol3/papers.cfm?abstract_id=2249909. Commented Oct 20, 2017 at 14:39

As a disclaimer: I didn't have time to read the paper carefully, but the authors seem to be simply using the big O notation, i.e.

$$f(x) = O(g(x))$$

if there exists some coinstant $M$ such that

$$|f(x)| \le |Mg(x)|$$

so $O(\cdot)$ drops the constant(s) from the function. So the equation says that the difference between the probability and $1$ is proportional to $T^{-\eta}$.

This notation is used to simplify the exposition of results involving asymptotic behaviour.

It is indeed plain old Big O Notation, as found in complexity and convergence.

What it (most likely) means is that the result was proved for a lower bound of the form $$1-(cT^{-\eta}+S)$$ where $c$ is a constant and $S$ is a collection of lower-order terms. The problem is that $c$ and/or $S$ are perhaps ugly and would mar their presentation.

Precisely because they are lower-order, if there are $n$ such terms, for sufficiently large $T$ we can state $$1-(cT^{-\eta}+S) \geq 1-\left((c+n)T^{-\eta}\right)$$ And by definition, $(c+n)T^{-\eta} = O(T^{-\eta})$ as $T\rightarrow \infty$ (and of course so does the smaller function $cT^{-\eta}+S$).

To sum up, they cannot write $$p\geq 1-T^{-\eta}$$ as that is a presumably better bound than what was actually proved. So

$$p\geq 1-O(T^{-\eta})$$ allows them to get away with an almost equally neat result.

That's the Big O notation.

You are correct with your interpretation.

$O(T^{-\eta})$ can be any function $f(T)$ such that for sufficiently large values of $T$,

$|f(T)| \leq M T^{-\eta}$,

for a certain constant $M$. So, yes: for large values of $T$,

$1 - O(T^{-\eta})$ will tend to 1.