A deterministic algorithm has one prescribed next step for each permitted input and current 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 elapsed time on different computers.
Binary search with a fixed midpoint rule is deterministic: every comparison determines which remaining interval is searched next. Quicksort with a fixed pivot-selection rule is also deterministic, even though different inputs can produce very different running times. 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, 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.
Articles by others on the same topic
There are currently no matching articles.