I had a fun talk about this with an interviewer once when they asked me about the runtime complexity of some algorithm.
Let \(f\) and \(g\) be eventually positive functions from \(\mathbb{R}_{\ge 0}\) to \(\mathbb{R}_{>0}\). Pick an unlimited hypernatural \(H\in{}^*\mathbb{N}\setminus\mathbb{N}\) (we write \(H\gg 1\) for short), and look directly at the ratio \(\frac{ {}^*f(H) }{ {}^*g(H) }.\)
Then the big O relations become simple checks on \(\frac{ {}^*f(H) }{ {}^*g(H) }\), and we require that the condition holds for every unlimited \(H\):
We have \(f\in O(g)\) if and only if there exists a standard constant \(C>0\) such that \(\frac{ {}^*f(H) }{ {}^*g(H) } \le C\). In math: \(f\in O(g)\ \iff\ \exists\ \text{standard } C>0:\ \frac{ {}^*f(H) }{ {}^*g(H) } \le C.\)
We have \(f\in \Omega(g)\) if and only if there exists a standard constant \(c>0\) such that \(\frac{ {}^*f(H) }{ {}^*g(H) } \ge c\). In math: \(f\in \Omega(g)\ \iff\ \exists\ \text{standard } c>0:\ \frac{ {}^*f(H) }{ {}^*g(H) } \ge c.\)
We have \(f\in \Theta(g)\) if and only if there exist standard constants \(0<c\le C<\infty\) such that \(c\le \frac{ {}^*f(H) }{ {}^*g(H) } \le C\). In math: \(f\in \Theta(g)\ \iff\ \exists\ 0<c\le C<\infty\ \text{standard}:\ c\le \frac{ {}^*f(H) }{ {}^*g(H) } \le C.\)
We have \(f\in o(g)\) if and only if \(\frac{ {}^*f(H) }{ {}^*g(H) } \approx 0\) (that is, the ratio is infinitesimal). In math: \(f\in o(g)\ \iff\ \frac{ {}^*f(H) }{ {}^*g(H) } \approx 0.\)
We have \(f\in \omega(g)\) if and only if \(\frac{ {}^*f(H) }{ {}^*g(H) }\) is unlimited. In math: \(f\in \omega(g)\ \iff\ \frac{ {}^*f(H) }{ {}^*g(H) } \text{ is unlimited}.\)
Examples
For \(f(x)=x^2\) and \(g(x)=x^3\), we compute \(\frac{ {}^*f(H) }{ {}^*g(H) } = 1/H\), which is infinitesimal. Therefore \(x^2\in o(x^3)\). In math: \(f(x)=x^2,\ g(x)=x^3:\ \frac{ {}^*f(H) }{ {}^*g(H) } = 1/H\approx 0\ \Rightarrow\ x^2\in o(x^3).\)
For \(f(x)=x^3\) and \(g(x)=x^2\), we compute \(\frac{ {}^*f(H) }{ {}^*g(H) } = H\), which is unlimited. Therefore \(x^3\in \omega(x^2)\), and hence \(x^3\in\Omega(x^2)\). In math: \(f(x)=x^3,\ g(x)=x^2:\ \frac{ {}^*f(H) }{ {}^*g(H) } = H\ \text{unlimited}\ \Rightarrow\ x^3\in \omega(x^2)\subseteq\Omega(x^2).\)
For \(f(x)=x+c\), where \(c\) is any standard real number, and \(g(x)=x\), we compute \(\frac{ {}^*f(H) }{ {}^*g(H) } = 1+\tfrac{c}{H}\). Since \(\tfrac{c}{H}\) is infinitesimal, we have \(\frac{ {}^*f(H) }{ {}^*g(H) } \approx 1\). Therefore \(x+c\in\Theta(x)\). In math: \(f(x)=x+c,\ g(x)=x:\ \frac{ {}^*f(H) }{ {}^*g(H) } = 1+\tfrac{c}{H}\approx 1\ \Rightarrow\ x+c\in\Theta(x).\)
The “for every unlimited \(H\)” condition encodes the usual “for all sufficiently large \(x\)” via transfer. A single infinite index can be fooled by oscillations; checking every unlimited \(H\) gives you the uniformity you need.
For example, let \(g(x)=x\) and define \(f\) by parity of the integer part:
- if \(\lfloor x\rfloor\) is even, set \(f(x)=x\);
- if \(\lfloor x\rfloor\) is odd, set \(f(x)=\dfrac{x}{\log(x+2)}\).
Then \(f\) is eventually positive, and the ratio \(\dfrac{f(x)}{g(x)}\) oscillates between \(1\) (on even blocks) and \(\dfrac{1}{\log(x+2)}\) (on odd blocks). A single check at an even unlimited \(H\) gives \(\dfrac{ {}^*f(H) }{ {}^*g(H) } = 1\) and could tempt you to say \(f\in\Theta(g)\). But along odd unlimited \(H\) we have \(\dfrac{ {}^*f(H) }{ {}^*g(H) } = \dfrac{1}{\log(H+2)}\approx 0\), so \(f\notin\Omega(g)\) and hence \(f\notin\Theta(g)\), even though \(f\in O(g)\). In math: along even \(H\), \(\frac{ {}^*f(H) }{ {}^*g(H) } = 1\); along odd \(H\), \(\frac{ {}^*f(H) }{ {}^*g(H) } = 1/\log(H+2)\approx 0\). Requiring the condition for every unlimited \(H\) prevents this mistake.