Stage-call, storage and arithmetic bounds for a finite SDC execution

By [F1], preliminary exits precede any instructed stage call. A run reaching and completing step 4 executes exactly one call for each of the $M$ stage indices. Step 5 is after this operation, so $K=0$ gives exactly $M$ calls and the stated exhausted status, without a residual test or accepted endpoint. The cancellation in [F2] removes both appearances of the fixed initial derivative from the forward recursion, so no separate $F_0$ call is instructed, including when a collocation node equals zero.

There are $2M^2$ entries in $Q,Q_{\mathrm{\Delta }}$, $M$ weights and $O(M)$ node data; optionally storing $Q-Q_{\mathrm{\Delta }}$ adds $M^2$ entries. Thus coefficient storage is $O(M^2)$. The two stage vectors and two derivative vectors have $4Md$ scalar entries, and accumulators and the endpoint require at most $O(Md)$ further entries. Buffer reuse in [F3] keeps this storage independent of $K$. Once $Q,b$ are available, computing the node differences, $Q_{\mathrm{\Delta }}$, $Q-Q_{\mathrm{\Delta }}$ and the maximum absolute row sums visits at most $O(M^2)$ entries, giving the asserted setup work, outside the excluded checks.

In a full sweep, [F2] reuses every old derivative and executes exactly one new derivative call for each stage, for $M$ new calls. Summing these disjoint calls over $s$ full sweeps and adding step 1.1 gives $M+sM=M(s+1)$. If the next stage is inadmissible after $p$ new derivative evaluations, it is rejected before its own evaluation and no remaining stage is evaluated; the count is consequently $M(s+1)+p$, with $p<M$. Here $s<K$, so $M(s+1)+p<M(K+1)$; without an incomplete sweep, $s\le K$ gives $M(s+1)\le M(K+1)$. Exits before step 4 also satisfy this bound by step 1.1. Equality holds when all $K$ sweeps complete. After $s$ full sweeps, the current loop index is $k=s-1$; on acceptance [F2] returns $U^{s-1}$ and its endpoint is a weighted sum of derivatives already in the old buffer. Thus endpoint formation makes no additional stage call and does not substitute $U^s$ for the returned stage vector.

At stage $i$, the two sums in [F3] contain at most $(i-1)+M\le 2M$ terms, each a scalar multiple of a $d$-vector. Direct scalar multiplication and accumulation cost $O(Md)$ arithmetic for that stage, hence $O(M^{2}d)$ for at most $M$ stages. Early exit evaluates only a prefix of these sums. Each completed residual computes $Md$ differences and squares, $M$ sums of $d$ squares, at most $M$ square roots, and a maximum over $M$ norms; this costs $O(Md)$ arithmetic and the stated additional operations. An accepted endpoint sums $M$ weighted $d$-vectors for $O(Md)$ arithmetic. There are at most $K$ attempted sweeps, at most $K$ residual tests and at most one accepted endpoint. Default predictor initialization takes $O(Md)$ scalar assignments. Adding this initialization, step 1.2 setup and the per-sweep work gives $O(M^2+(K+1)M^{2}d)$ because $M,d\ge 1$; at most $KM$ square roots are used. The same bounds hold through any earlier exit. No work or storage from an excluded task has been charged, and exact-real counts provide no assertion about floating-point error.