Asymptotic comparison of resource bounds

Let $f,g:\mathbb{N}\to [0,\mathrm{\infty })$. We say that $f$ is asymptotically bounded by $g$, and write $f(n)=O(g(n)),$ when there exist constants $c>0$ and $n_0\in \mathbb{N}$ such that $f(n)\le cg(n)(n\ge n_0)\mathrm{.}$

We say that two bounds are of the same asymptotic order when each is $O$-bounded by the other. Fix further bounds $t,s:\mathbb{N}\to [0,\mathrm{\infty })$.

If $M$ is a machine in the sense of Worst-case time and space complexity of a machine and halts on every input, then its worst-case resource functions are defined at every input length, and:

• $M$ has time complexity $O(t(n))$ when ${\mathrm{Time}}_M(n)=O(t(n))$;
• $M$ has space complexity $O(s(n))$ when ${\mathrm{Space}}_M(n)=O(s(n))$.

• These comparisons forget constant factors and finite prefixes.

• Later invariance statements are about preservation of classes under this asymptotic relation, not equality of exact running times.