# "Big O" notation

To work out the order of a function $$f(x)$$, I used to just look at the leading term of $$f(x)$$ (we call $$g(x)$$) and we would have $$\forall x \quad \exists C$$ such that $$f(x) < Cg(x)$$.

I was just given the definition:

Given two functions $$F(t)$$ and $$G(t)$$, we say that $$F(t) = O(G(t))$$ if $$\exists C, \epsilon$$ between $$(0, \infty)$$ such that $$|t|<\epsilon \implies |F(t)| \leq C|G(t)|$$.

Using this definition, $$t^2$$ is $$O(t)$$ and $$t$$ is not $$O(t^2)$$ - is this right? I would've said the other way around.

• I think this is for the range $(0, \epsilon)$ that $t^2 \in O(t)$ would hold, for $\epsilon \leq 1$ Jan 15, 2021 at 9:56
• @IntegrateThis but the definition says that $\epsilon$ is between $(0, \infty)$.. Jan 15, 2021 at 10:00
• It depends if you look at the asymptotic at $0$ or at $\infty$. Jan 15, 2021 at 10:20
• At $0$, $t$ is not $O(t^2)$. Otherwise, what could you choose as a constant $C$? Jan 15, 2021 at 10:22

$$F(t) = O(G(t)) \iff$$ there is a neighborhood $$U$$ of $$0$$ such that $$\frac{F(t)}{G(t)}$$ is bounded on $$U.$$

$$\frac{t^2}{t}=t$$ is bounded in a neighborhood of $$0$$, hence $$t^2$$ is $$O(t)$$.

$$\frac{t}{t^2}= \frac{1}{t}$$ is not bounded in a neighborhood of $$0$$, hence $$t$$ is not $$O(t^2)$$.

• Thank you for your explanation. I guess I am unsure why we are assuming $\epsilon$ is close to $0$ if the definition says it is between $(0, \infty)$. Jan 15, 2021 at 10:06
• My understanding was like Drake's answer. Why is this different? Jan 15, 2021 at 13:17
• @user572780 Because the criterion becomes easier to satisfy the smaller $\epsilon$ is, essentially. This is also suggested by the use of the symbol $\epsilon$ in the first place.
– Ian
Jan 15, 2021 at 13:19
• @Ian That makes sense, thank you. I haven't really thought about that before. So 'Big O' notation depends on where t is trending towards. Jan 15, 2021 at 13:28

I am not sure if I understand your definition.

The correct formal definition is: $$f \in O(g) \iff \exists C > 0 \; \exists x_0 > 0 \; \forall x > x_0: |f(x)| \leq C \cdot |g(x)|$$

If I now use your example we get the following:

• $$f(t) = t$$
• $$g(t) = t^2$$

Clearly $$f(t) \in O(g(t)) \iff t \in O(t^2)$$ because:

• $$C = 2 > 0$$
• $$x_0 = 1 > 0$$
• $$\forall x > x_0 = 1: |t| \leq 2 \cdot |t^2|$$, since every number $$\forall t \geq 1: t \leq t^2$$.

For showing that $$t^2 \in O(t)$$, we cannot find a $$C > 0$$ and a $$x_0 > 0$$, such that $$\forall x > x_0: |t^2| \leq C \cdot|t|$$, since the quadratic growth is just to big. So $$t^2 \not \in O(t)$$.

• What you wrote is for limits st infinity. The OP is doing limits at zero.
– Ian
Jan 15, 2021 at 13:16