Abstract
Two simply typed term systems $\sf {PR}_1$ and $\sf {PR}_2$ are considered, both for representing algorithms computing primitive recursive functions. $\sf {PR}_1$ is based on primitive recursion, $\sf {PR}_2$ on recursion on notation. A purely syntactical method of determining the computational complexity of algorithms in $\sf {PR}_i$ , called $\mu$ -measure, is employed to uniformly integrate traditional results in subrecursion theory with resource-free characterisations of sub-elementary complexity classes. Extending the Schwichtenberg and Müller characterisation of the Grzegorczyk classes ${\mathcal{E}}_n$ for $n\ge 3$ , it is shown $\mathcal{E}_{n+1} = \mathcal{R}^n_1 $ for $ n\ge 1 $, where $ \mathcal{R}^n_i$ denotes the \emph{ $n$ th modified Heinermann class} based on $\mu$ . The proof does not refer to any machine-based computation model, unlike the Schwichtenberg and Müller proofs. This is due to the notion of modified recursion lying on top of each other provided by $\mu$ . By Ritchie's result, $\mathcal{R}^1_1$ characterises the linear-space computable functions. Using the same method, a short and straightforward proof is presented, showing that $\mathcal{R}^1_2$ characterises the polynomial time computable functions. Furthermore, the classes $\mathcal{R}^n_2$ and $\mathcal{R}^n_1$ coincide at and above level 2