0

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)$?

Matteo
  • 6,581
dawen
  • 395
  • 1
    Roughly speaking, the graph of $f(x)$ will eventually lie under the graph of $k\sqrt{x}$ for some constant $k$ – AlvinL Aug 17 '19 at 10:32

1 Answers1

3

$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}$.

Jean-Claude Arbaut
  • 23,277
user6767509
  • 437