Classical query complexity

For a classical query algorithm Classical query algorithm at input length $n$, its worst-case classical query cost is the maximum number of oracle calls over every promised instance and every random tape. When there are no promised instances of length $n$, define this cost to be $0$. If those counts are not uniformly bounded, the cost is infinite. One query returns the full value $f_z(x)$, regardless of its bit width. Expected-query bounds are reported separately using Expected query cost from finite execution prefixes.

For a bounded-error classical solver, the query cost is still worst-case over inputs and random tapes; the success requirement is the per-instance probability in Worst-case bounded-error correctness. Distributional input averages and expected query counts are different quantities.