Consider the relation R on the set of functions defined by $(f, g) ∈ R$ if and only if $f(x)$ is $\mathcal{O}(g(x))$.

(a) Show that $R$ is transitive. (b) Show that $R$ is reflexive. (c) Is $R$ symmetric? Either prove that it is, or find two functions f and g so that $(f, g) ∈ R$ but $(g, f)\notin R$.

<aside> 💡 (a) If $R$ is transitive: if $(f,g) \in R$ and $(g,h) \in R$, then $(f,h) \in R$.

Suppose $(f,g) \in R$, which means that $f(x)$ is $\mathcal{O}(g(x))$. Similarly, suppose $(g,h) \in R$, which means that $g(x)$ is $\mathcal{O}(h(x))$.

To show that $(f,h) \in R$, we need to show that $f(x)$ is $\mathcal{O}(h(x))$.

Since$f(x)$ is $\mathcal{O}(g(x))$, there exist constants $C_1$ and $x_1$ such that $|f(x)| \leq C_1 |g(x)|$ for all $x \geq x_1$.

Similarly, since $g(x)$ is $\mathcal{O}(h(x))$, there exist constants $C_2$ and $x_2$ such that $|g(x)| \leq C_2 |h(x)|$ for all $x \geq x_2$.

Let $x_0 = \max(x_1, x_2)$. Then for all $x \geq x_0$, we have:

$$ ∣f(x)∣≤C1∣g(x)∣≤C1C2∣h(x)∣ $$

which shows that $f(x)$ is $\mathcal{O}(h(x))$. Therefore, $(f,h) \in R$, and $R$ is transitive.

(b) To show that $R$ is reflexive, we need to show that for any function $f, (f,f) \in R$, which means that $f(x)$ is $\mathcal{O}(f(x))$.

This is trivially true since $f(x) = 1 \cdot f(x)$ for all $x$, and $1$ is a constant.

Therefore, $f(x)$ is $\mathcal{O}(f(x))$, and$(f,f) \in R$.

Thus, $R$ is reflexive.

(c) $R$ is not symmetric. To see why, consider the functions $f(x) = x$ and $g(x) = x^2$.

We have $f(x)$ is $\mathcal{O}(g(x))$ since $|f(x)| \leq |g(x)|$ for all $x \geq 0$. However, $g(x)$ is not $\mathcal{O}(f(x))$ since for any constant $C$, we can find $x$ such that $g(x) > C \cdot f(x)$. For example, if we take $C = 1$ and $x = 1$, then $g(x) = 1$ and $f(x) = 1$, so $g(x) > C \cdot f(x)$.

Therefore, $(f,g) \in R$ but $(g,f) \notin R$, and $R$ is not symmetric.

</aside>