Deterministic and Non-Deterministic Algorithms

by codecrucks · Published 16/02/2023 · Updated 16/02/2023

Deterministic and Non-Deterministic Algorithms differ in the way they produce outputs on multiple executions.

Deterministic Algorithms

If we run deterministic algorithms multiple times on the same input, they produce the same result every time.
Deterministic algorithms are typically represented by the state machine, where the machine moves from one state to another state on a specific input.
The underlying machine always goes through the same states during execution.
Finding a random number is deterministic, it always returns a random number. Finding odd or even, sorting, finding max, etc. are deterministic. Most of the algorithms used in practice are deterministic in nature.

The non-deterministic algorithm works on guessing. For some input, nondeterministic algorithms may produce different outcomes every time.
The nondeterministic algorithm operates in two phases: guessing and verification. After guessing the answer, the algorithm verifies its correctness.
In the non-deterministic algorithm, each state has a probability of a different outcome on the same input. The vending machine is an example of the deterministic approach, in which the outcome against given input is always deterministic.
Randomly picking some element from the list and checking if it is maximum is non-deterministic.
The nondeterministic algorithm operates in two stages.
Non-deterministic (guessing) stage : For input instance I, some solution string S is generated, which can be thought of as a solution.
Deterministic (verification) stage : I and S are given as input to the deterministic algorithm, which returns “Yes” if S is a solution for input instance I.
Non-deterministic algorithm behaves differently for the same input on different runs. The concurrent algorithm can produce different outputs for the same input on different runs due to the race condition.
Selecting random permutations of n numbers and checking the order of numbers is non-deterministic. The first permutation may be (1, 2, 3), next may be (3, 1, 2), next may be (2, 3, 1) etc.