Complexity of Initial-Value Problems for Ordinary Differential Equations of Order k - Different Models of Computation

We study the e-complexity of initial-value problems for scalar equations of higher order. We consider three settings: the deterministic worst-case setting with standard and linear information, the randomized and the quantum settings. In each setting we establish upper and lower complexity bounds and construct (almost) optimal algorithms adjusted to scalar equations of higher order. These algorithms do not require passing to a system of first order equations. We show in the deterministic setting with linear information the strong dependence of the E-complexity on the order of the equations. We also show the speed-up of randomized algorithms by 1/2, and of quantum algorithms by I in the exponent in comparison to the deterministic case.