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
    $\begingroup$ Roughly speaking, the graph of $f(x)$ will eventually lie under the graph of $k\sqrt{x}$ for some constant $k$ $\endgroup$ – Alvin Lepik Aug 17 at 10:32

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.