Z drugiej strony, jeśli będziemy sprawdzać losowe elementy, dla dowolnej tablicy z dużym prawdopodobieństwem trafimy bardzo szybko na literę „a".
Powyższy przykład opisuje algorytm, który zawsze zwraca prawidłową odpowiedź, ale jego czas działania nie jest z góry ustalony. Algorytmy tego typu nazywane są algorytmami Las Vegas. Drugim typem algorytmów są algorytmy Monte Carlo, które zawsze kończą się w ustalonym czasie, ale mogą z pewnym prawdopodobieństwem zwrócić zły wynik bądź zwracają wynik tylko z pewną dokładnością.
Algorytmy randomizowane są szczególnie użyteczne, jeśli rozważamy sytuację, w której jakiś „przeciwnik" próbuje zmusić algorytm do dłuższego działania. Ma to miejsce na przykład w kryptografii i bezpieczeństwie komputerowym
Złożoność Teoria złożoności obliczeniowej Kołmogorowa definiuje algorytmy probabilistyczne przy użyciu pojęcia probabilistycznej maszyny Turinga. Model ten definiuje odpowiednie klasy złożoności obliczeniowej, analogicznie do klasycznej maszyny Turinga. Przykładowo do klasy złożoności RP należą problemy, dla których istnieje algorytm probabilistyczny działający w czasie wielomianowym, który negatywne przypadki zawsze odrzuca, a pozytywne akceptuje z prawdopodobieństwem co najmniej 50%. Dualną do tej klasy jest klasa Co-RP, a przecięcie tych dwóch klas nazywane jest klasą BPP.