next up previous
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(NLK2). The latter is derived from repeating the iterative step for t=1, 2, ..., N, calculating Ut(st) for K states, and a complexity of KL for the max operation.



Yishay Mansour
1999-11-18