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