0

Say I have a function, $g:\mathbb{R} \mapsto \mathbb{R}$. Then would the set $O(g)$ be defined (as explicitly as possible) as: $$O(g) = \{ f:\mathbb{R} \mapsto \mathbb{R} \space|\space \exists C \in \mathbb{R}^{+}:\exists n_{0} \in \mathbb{R}: \forall n>n_{0}:|f(n)|\leq C\cdot|g(n)|\}$$

That is, do all the functions in $O(g)$ need to be the same 'type' of function as $g$, i.e. do all $f$ in $O(g)$ necessarily have to map from $\mathbb{R} \mapsto \mathbb{R}$ as well?

James Hiew
  • 155

1 Answers1

1

For the notation to make sense, it is sufficient that both are defined in a neighbourhood $\infty$ (the point of interest here), i.e. both domains must contain an interval $(x_0,\infty)$.

Hence we can say things like

  • $\ln x = O(x)$
  • $\frac1{x^2+1}= O(\sqrt x)$

But can one also say

  • $42 = O(\tan^2x+1)$?

One may argue that in those places where $\tan^2x+1$ is not defiend, it "should" be $+\infty$, i.e. we may wish to consider functions to $\mathbb R\cup \{\infty\}$ ...

Hagen von Eitzen
  • 374,180
  • It is interesting to consider the big-O set of a discontinuous function like $\tan^{2} x + 1$. In computer science, in the context of asymptotics the focus is generally on functions mapping to $\mathbb{N}$. – James Hiew Oct 20 '14 at 12:19