What is bounded by $O(T)$ mean?

35 Views Asked by At

I have come across something like $f(T)$ be bounded by $O(\sqrt{T})$ many times in optimization context.

usually, $f(T)$ don't have an explicit form.

If $f(T)$ do have an explicit form, say $f_1(T)=\frac{1}{2}\sqrt T$ and $f_2(T)=\frac{3}{2}\sqrt T$, can we say $f_1(T)$ and $f_2(T)$ are bounded by $O(\sqrt T)$?

1

There are 1 best solutions below

0
On BEST ANSWER

$f(x) \in O(g(x))$ if there exists $c > 0$ (e.g., $c = 1$) and $x_0$ (e.g., $x_0 = 5$) such that $f(x) \le cg(x)$ whenever $x \ge x_0$. You can look this up on Wikipedia ("big $O$ notation").

So for $f_2(T)$, $c=3/2$ and $g(T)=\sqrt{T}$.