## How do we express the efficiency of an algorithm involving random events?

To illustrate how we do this, let us do this for the input search algorithm, both for the Classical Turing machine (CTM) and the Probabilistic Turing Machine (PTM). In both cases, it makes sense to express the number of steps needed to find the input as functions $t_{\textrm{CTM}}(d)$ and $t_{\textrm{PTM}}(d)$ of the distance $d$ of…