Operating System

Explain about deterministic algorithm evaluation model ?

A deterministic algorithm is one where, given a particular input, the algorithm will always produce the same output and follow the same sequence of states. It operates under the principle of predictability and consistency. The outcome of a deterministic algorithm can be precisely determined based on its input

A deterministic algorithm is deterministic. If you give me some inputs, I can tell you exactly what the algorithm will output (or at least that it will be consistent) no matter how many times you rerun the algorithm.

Simple gradient descent is a good example. Given a slope function, a starting point, and a number of iterations, the answer will always be the same for well-defined functions.

A non-deterministic algorithm is the opposite of this.

Non-deterministic algorithms are tough to find in nature, but one good example lies in quantum mechanics. We can’t determine certain properties of identical subatomic particles without measuring them. That is to say, given the exact same input, we still don’t know what the output will be.

Difference between Deterministic and Non Deterministic Algorithm

The primary distinctions between deterministic and non-deterministic algorithms are as follows.

Key AspectDeterministic AlgorithmNon-deterministic Algorithm
DefinitionDeterministic algorithms produce uniquely defined results. They perform a fixed number of steps and always finish with an accept or reject state with the same result.Non-deterministic algorithms do not produce uniquely defined results. The outcome may be random or not uniquely determined.
ExecutionIn deterministic algorithms, the target machine executes the same instructions and yields the same outcome, independent of the way or process of execution.In non-deterministic algorithms, the machine executing each operation can choose any of several outcomes, subject to a determination condition defined later.
TypeDeterministic algorithms are classified as reliable algorithms. They consistently produce the same output for the same input instructions.Non-deterministic algorithms are considered non-reliable algorithms because they may produce different outputs for the same input.
Execution TimeDeterministic algorithms typically execute in polynomial time since the outcome is known and consistent across executions.Non-deterministic algorithms often cannot be executed in polynomial time due to their unpredictable nature.
Execution PathIn deterministic algorithms, the execution path remains the same in every execution.In non-deterministic algorithms, the execution path varies between executions and may take different, random paths.

Leave a Reply

Your email address will not be published. Required fields are marked *