Understanding double asymptotics

72 Views Asked by At

Suppose I have a double sequence $x_{i,t}$ of numbers where $i=1,\dots,n$ and $t=1,\dots,T$ and a function $f(n,T)$ of these numbers, e.g. $f(n,T)=\sum_{t=1}^{T} \sum_{i=1}^{n} x_{i,t} / nT$.

The paper am reading is interested in the quantity $f(n,T)$ as $n,T\to \infty$ with $n=O(T)$.

Question: What is the precise meaning of $n=O(T)$ in this context?

Am confused because neither $n$ or $T$ is a function of the other and usually we have expressions like $x_n=O(y_n)$ with a common index $n$.

1

There are 1 best solutions below

2
On BEST ANSWER

Casually speaking, $n=O(T)$ means that the growth of $n$ is "at most" the growth of $T$ in asymptotic manner. If both $n$ and $T$ are functions (or sequences, in your case perhaps) of some $k$, then you can imagine their graphs that as $n$ grows, its tail behaviour would be smaller or the same as that of $T$. For example, if $n=\sqrt k$ and $T=k$, then it is valid to claim that $n=O(T)$.

Big O notation is somewhat a neat way to quantify functions comparison in terms of their growth rate.