** Next:** Example: The Recruiting Problem
** Up:** An Algorithm for Constructing
** Previous:** An Algorithm for Constructing

###

Computational Complexity

Let *K*=|*S*| and *L*=|*A*|, then the time complexity of the described algorithm is
*O*(*NLK*^{2}). The latter is derived from repeating the iterative step for
*t*=1, 2, ..., *N*, calculating *U*_{t}(*s*_{t})
for *K* states, and a complexity of *KL* for the max operation.

*Yishay Mansour*

*1999-11-18*