Разница между детерминированным и недетерминированным исполнением программ заключается в том, что в детерминированном исполнении программа следует по одному пути для заданного ввода, а обработка одних и тех же входных данных всегда приводит к одинаковому результату. 12 Каждый шаг заранее предопределён. 2

Недетерминированное исполнение допускает несколько путей или вариантов выбора во время выполнения программы. 1 Это означает, что при вводе программа может одновременно исследовать различные возможности. 1 Обработка одних и тех же входных данных может приводить как к одинаковым, так и к разным результатам. 2

Также детерминированные модели фокусируются на сценарии наихудшего случая, обеспечивая верхнюю границу времени, необходимого для решения проблемы для любого размера входных данных. 1 Недетерминированные модели рассматривают наилучший сценарий, когда программа делает оптимальный выбор на каждом этапе, и обеспечивают нижнюю границу временной сложности. 1