Intermediate · Research
Nondeterministic algorithm
Visual diagram · (in preparation) · Math · (in preparation) · Worked example · 3 difficulty levels.
TL;DR. An algorithm that can produce different outputs for the same input on different runs.
Technical Definition
An algorithm that can produce different outputs for the same input on different runs.
How it works
A nondeterministic algorithm differs from a deterministic one by its potential to exhibit varying behaviors even when provided with identical inputs across multiple executions. This characteristic is a key concept in computational complexity theory, particularly when analyzing the efficiency of algorithms.
Related Concepts
- Algorithm — A finite, well-defined sequence of steps used to learn from data or solve a computational problem.
- Computational complexity theory — Classifying computational problems by difficulty and understanding the relationships between different problem classes.