deterministic vs nondeterministic computation

A deterministic algorithm is utterly predictable: give it the same input and it always does the same thing and returns the same answer, like a vending machine that hands you the same snack for the same buttons every time. Most algorithms you write are deterministic. The interesting alternatives loosen this in two very different ways — one practical (randomized algorithms, which flip coins) and one theoretical (nondeterministic computation, which magically guesses) — and it pays to keep them apart, because they sound similar but mean different things.

A deterministic algorithm's next step is fully fixed by its current state and input; its whole run is a single, repeatable path. A randomized algorithm is allowed to make genuinely random choices along the way — it has a source of coin flips — so the same input can lead to different runs. We then talk about its expected running time (its average over the coin flips) or its probability of being right. Randomized quicksort is the classic case: by picking the pivot at random it runs in O(n log n) expected time, where the expectation is over the random pivots, not over the inputs. Nondeterministic computation is a different, idealized beast: imagine a machine that, at each choice point, could explore all options at once and is declared to accept if any single sequence of guesses leads to acceptance. This is not a real device you can build; it is a thought-tool for classifying problem difficulty, and it is the "N" in the complexity class NP.

Keeping the three straight prevents real misunderstandings. Randomized does not mean "sloppy" or "usually right" in a vague way — its guarantees are precise probabilistic statements, and crucially, randomized quicksort's worst case is still O(n^2); only its expected time is O(n log n). Nondeterministic does not mean "random" at all — the magical guessing of an NP machine is not something hardware can do, and "NP" is emphatically not a claim that a problem needs exponential time, only that a proposed solution can be checked quickly. Confusing nondeterminism with randomness, or expected time with worst-case time, is one of the most common beginner errors in this whole subject.