# Deterministic and Non-Deterministic Algorithms

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.

## Non-deterministic Algorithms

• 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.