2

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.

user572780
  • 338

2 Answers2

4

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

user572780
  • 338
Fred
  • 77,394
  • 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)$. – user572780 Jan 15 '21 at 10:06
  • My understanding was like Drake's answer. Why is this different? – user572780 Jan 15 '21 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 '21 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. – user572780 Jan 15 '21 at 13:28
0

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

Drake
  • 1