Randomized algorithm

Randomized algorithms use random bits for expected polynomial time

Randomized algorithms incorporate randomness to improve average-case performance. They often use uniformly random bits as an auxiliary input to guide their behavior, aiming for good performance across all possible random choices. This randomness helps in achieving expected polynomial time for solving problems.

Example

Quicksort is a Las Vegas algorithm that uses random bits to select pivot elements, aiming for expected polynomial time complexity.

Remember this

Understanding the use of random bits in randomized algorithms is crucial for designing efficient algorithms that perform well on average, even though they may not guarantee the best-case performance in every scenario.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

Shor's algorithm

Shor's algorithm factors integers in polynomial time on a quantum computer

Kolmogorov complexity

Kolmogorov complexity is uncomputable

Computational complexity of matrix multiplication

O(n³) naive matrix multiplication

the Johnson-Lindenstrauss lemma says

Can we shrink big data without losing important details?

Overlapping subproblems

Ever calculated a huge Fibonacci sequence by hand?

Shannon's source coding theorem: you can't compress below entropy

Can you squeeze endless text into fewer bits without losing anything?

Swipe through 100 ML concepts daily

Open Pocket Polymath