Randomized vs Deterministic Algorithms

 

Randomized vs Deterministic Algorithms

Aspect	Deterministic Algorithm	Randomized Algorithm
Basic idea	Follows a fixed sequence of steps to solve a problem.	Uses random choices during the execution of the algorithm.
Decision making	Decisions are completely predictable.	Some decisions are based on random numbers or random choices.
Output	Produces the same output for the same input.	Output or the path taken may vary between different runs, depending on the type of randomized algorithm.
Execution	Follows the same execution path for the same input.	May follow different execution paths for the same input.
Accuracy	Usually produces an exact and predictable result.	May produce an exact result or an approximate result, depending on the algorithm.
Running time	Usually predictable for a given input.	Running time may vary because of random choices.
Complexity	Can sometimes be more difficult to design for complex problems.	Randomness can simplify the algorithm or help avoid unfavorable cases.
Example	Binary search, merge sort, calculating the total price of items.	Randomized Quicksort, random sampling, Monte Carlo simulation.
Use	Used when accuracy, consistency, and predictability are important.	Used when efficiency, large search spaces, or uncertainty make deterministic methods less practical.
Simple example	Add the prices of all items in a shopping cart to get the exact total.	Randomly select 200 customers from 10,000 customers to estimate overall satisfaction.

In Simple Words

Deterministic algorithm:

Same input → Same decisions → Same result

Randomized algorithm:

Same input → Random choices → Possibly different execution/result

Example:

If the college wants to estimate student satisfaction, randomly selecting a representative group of students and using their responses is a randomized approach.

If a college wants to include every student is a deterministic approach.