= Deterministic algorithm
A <deterministic algorithm> has one prescribed next step for each permitted <input> and current <state (computer science)>[computational state]. Thus the same <input> and initial state give the same <execution trace> and, if execution terminates, the same <output>. This is a statement about the abstract transition rules, not about identical <running time>[elapsed time] on different computers.
<Binary search> with a fixed midpoint rule is <deterministic algorithm>[deterministic]: every comparison determines which remaining interval is searched next. <Quicksort> with a fixed pivot-selection rule is also <deterministic algorithm>[deterministic], even though different <inputs> can produce very different <running time>[running times]. <deterministic algorithm>[Determinism] therefore does not imply a constant or small <time complexity>.
A <randomized algorithm> additionally receives random choices. Fixing its entire random-choice sequence makes its subsequent execution <deterministic algorithm>[deterministic], but averaging over those choices is essential to its randomized guarantees. A <Nondeterministic Turing machine> is a different mathematical model: its branches describe possible computation paths, rather than a <probability distribution> supplied by an implementation.
Back to article page
