2
$\begingroup$

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.

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

2 Answers 2

4
$\begingroup$

With your definition:

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

$\endgroup$
4
  • $\begingroup$ 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)$. $\endgroup$
    – user572780
    Jan 15, 2021 at 10:06
  • $\begingroup$ My understanding was like Drake's answer. Why is this different? $\endgroup$
    – user572780
    Jan 15, 2021 at 13:17
  • $\begingroup$ @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. $\endgroup$
    – Ian
    Jan 15, 2021 at 13:19
  • $\begingroup$ @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. $\endgroup$
    – user572780
    Jan 15, 2021 at 13:28
0
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .