Why $2R\sigma\sqrt{T+logT+1}=\tilde{{O}}(\sigma\sqrt{T})$?
What is $\tilde O$? There are two different definitions.


According to exercise 3.5 of Introduction to Algorightms by Corman et al., $\tilde O$ can mean $O$ with logarithmic factors ignored: $$\tilde O(g(n))= \{f(n): \text{there exist nonnegative constant } k \\ \text{ and positive constants } c, k, \text{ and }n_0
\text{ such that }\\ 0\le f(n)\le cg(n)(\log n)^k\text{ for all }n\ge n_0\}$$
According to Wikipedia entry, $f(n) = \tilde O(g(n))$ is shorthand for $f(n) = O(g(n)\left(\log g(n)\right)^k)$ for some $k$.


For any value $x&gt;0$, $x^0=1$. If we take $k=0$ simply, we can see that for either definition,
$$f(T)=\sqrt{2}R\sigma\sqrt{T+\log T+1}=O(\sigma \sqrt{T}) =O(\sigma \sqrt{T}\,1)=\tilde{O}(\sigma\sqrt{T})$$



Here is the explanation for the second equality in the above equation.

$\log T=o(T) \Rightarrow
T+\log T+1=\Theta(T) \Rightarrow \sqrt{T+\log T+1}=\Theta(\sqrt T)$

W can also proceed more rigorously, using L'Hôpital's rule once.

$$\lim_{T\to\infty}\frac{\sqrt{T+\log T+1}}{\sqrt T} = \sqrt{\lim_{T\to\infty}\frac{T+\log T+1}{T}} = \sqrt{\lim_{T\to\infty}\frac{1+\frac1T}{1}}=1$$