You can obtain the equations and switching times necessary to compute any arbitrary trajectory point in constant time (per degree of freedom). (EDIT: Assuming your constraints (min/max velocity and acceleration) are constant throughout the entire trajectory.)
What Jaci accelerated was the arc-length parameterization of splines, which is a necessary first step to obtain a uniformly-spaced trajectory that can then be time-parameterized with a motion profile. Parameterizing a spline by arc length involves evaluating an integral that generally cannot be evaluated analytically, so there is a tradeoff between accuracy and speed that must be made in coming up with a numerical solution.
Difficult integrals arise all the time in real-world engineering, and depending on the context one may use any of a number of techniques to evaluate them. Riemann sums (what Jaci was using) are a simple technique, though it may require very fine sampling to work well. Other techniques include
Euler Method or higher-order
Runge-Kutta methods.