Algorytmy, które nie są deterministyczne W informatyce bada się również algorytmy nienależące do tej klasy. Przykładami takich algorytmów są: niektóre algorytmy równoległe i rozproszone – w których interakcja pomiędzy niezależnie wykonywanymi obliczeniami może prowadzić do różnych rezultatów, algorytmy probabilistyczne – w których używane są ciągi losowych (lub pseudolosowych) bitów, algorytmy kwantowe – w których do obliczeń wykorzystywane są zjawiska kwantowe.
Wady algorytmów deterministycznych Istnieje wiele problemów, dla których nie znamy efektywnych deterministycznych algorytmów. Przykładowo sprawdzenie, czy dana liczba jest pierwsza, można przeprowadzić bardzo efektywnie za pomocą prostych probabilistycznych algorytmów, znanych od lat siedemdziesiątych (np. test Millera-Rabina). Algorytm deterministyczny dla tego problemu został znaleziony dopiero w 2002 r. (patrz test pierwszości AKS) i jest bardziej skomplikowany i mniej efektywny.