The \df{time complexity} of a~decision tree is defined as its depth. It therefore
bounds the number of comparisons spent on every path. (It need not be equal since
some paths need not correspond to an~actual computation --- the sequence of outcomes
-on the path could be unsatifisfiable.)
+on the path could be unsatisfiable.)
A~decision tree is called \df{optimal} if it is correct and its depth is minimum possible
among the correct decision trees for the given graph.