CMP.1:4.5 - Derive the cost that can change the choice

When cost matters, include input conversion, query size, solver calls and answer recovery under a named computational model. If conversion costs T_f(n), its output has size at most m(n), B costs T_B(m(n)), and recovery costs T_r(n,m(n)) including the returned answer size relevant to it, the one-query construction has the corresponding total bound:

T_A(n) <= T_f(n)+T_B(m(n))+T_r(n,m(n)).

If the answer size is not bounded through these arguments, include it explicitly. For several queries, sum the costs of their construction, calls and recovery, including any adaptive work between calls. Analyze peak simultaneous storage separately from total work.

The representation matters. A quantity written with n bits can have a value exponential in n; enumerating that many states changes the cost claim. Exact rational operations also have costs depending on operand length when bit complexity is the model.

Use the result to choose or reject the reduction for the current resources. Another solver, a smaller representation or a different computational construction can preserve the answer while changing cost. C.29.2 supplies the surrounding resource and accuracy formulation.