How does summation work on big O notation

Question

In an article I'm reading (http://www.jmlr.org/papers/volume13/dekel12a/dekel12a.pdf) it says:

"It is well-known that the optimal regret bound [...] is $O(\sqrt m)$"

Then:

"[in a network,] assuming that each node processes $m/k$ inputs, the expected regret per node is $O(\sqrt \frac{m}{k})$. Therefore, the total regret across all k nodes is $O(\sqrt km)$".

The second part of this statement does not seem very obvious to me, can someone explain how they got this result?

Thanks!

Answer 1

Formally, if you have $f\in\mathcal{O}(g)$, by definition $$\limsup_{n\rightarrow\infty}\left|\frac{f(n)}{g(n)}\right|<\infty\text{.}$$

You can trivially get $$\limsup_{n\rightarrow\infty}\left|\frac{\sum_{i=1}^kf(n)}{kg(n)}\right|<\infty$$ as the same limit, so adding $k$ copies of $f$ means you are now $\in\mathcal{O}(kg)$. Notably, this works even if $k$ itself varies.

They're just summing expectations by linearity, $k\sqrt{\frac{m}{k}}=\sqrt{km}$.

Answer 2

Formal definition of the big O notation, taking non negative sequences, is $$O(g) = \left\lbrace f:\exists C > 0, \exists N \in \mathbb{N}, \forall n (n > N \& n \in \mathbb{N}) (f(n) \leqslant C \cdot g(n)) \right\rbrace$$ To emphasize variable against which is big-$O$ defined, usually is used indication $n \to \infty$. IMHO this definition have superiority compared to definition by fraction, because last one lost sense in case when denominator have $0$'s in sub sequence of $\mathbb{N}$.

So any equality, which uses O-big, and especially on both sides of equality, can be viewed as equality between sets. Also, let me notice, that equality type $f=O(g)$ is quite different from type $O(f)=O(g)$. First means "$\in$", while under second we understand "$\subset \land \supset$". There can be proved some basic properties: $$f \cdot O(g) =\{f \} \cdot O(g)= O(f \cdot g) $$ for $K>0$ constant $$K \cdot O(g) = O(K \cdot g)= O( g) $$

Allow me repeat, that, for example, last equality we can understand as equality between sets i.e. in both directions.

So, in your paper (167p), when we consider $m$ as variable against which is big-$O$ is defined, symbols $O( \sqrt{m}) = O\left(\sqrt{\frac{m}{k}}\right)= O( \sqrt{k \cdot m}) $ are different designations for one and same set. Writing constant inside big-$O$ from exact formal view is meaningless, but often used, when authors want to keep in one record as big-$O$ generality, so coefficient for exact estimation.