# What is the time complexity of the value iteration algorithm?

Recently, I have come across the information (lecture 8 and 9 about MDPs of this UC Berkeley AI course) that the time complexity for each iteration of the value iteration algorithm is $$\mathcal{O}(|S|^{2}|A|)$$, where $$|S|$$ is the number of states and $$|A|$$ the number of actions.

Here is the equation for each iteration:

$$V_{k+1}(s) \gets \max_a \sum_{s'} T(s, a, s') [R(s, a, s') + \gamma V_k(s')]$$

I could't understand why the time complexity is $$\mathcal{O}(|S|^{2}|A|)$$. I searched the internet, but I didn't find any good explanation.

The update equation for value iteration that you show is time complexity $$O(|\mathcal{S}\times\mathcal{A}|)$$ for each update to a single $$V(s)$$ estimate, because it iterates over all actions to perform $$\text{max}_a$$ and over all next states for $$\sum_{s'}$$.
The sources you have found are probably counting an entire sweep through the state space as an "iteration" i.e. $$\forall \space s \in \mathcal{S}: V_{k+1}(s) \leftarrow \text{max}_a \sum_{s'} T...$$ That adds another factor of $$|\mathcal{S}|$$ making the overall complexity $$O(|\mathcal{S}\times\mathcal{S}\times\mathcal{A}|)$$ or $$O(|\mathcal{S}|^2|\mathcal{A}|)$$
• @ShifatEArman: Yes. Also, in practice $\sum_{s'}$ may not be a full multiplier of $|\mathcal{S}|$ for deterministic or easy-to-calculate transitions. But in the general case it is. – Neil Slater Nov 17 '18 at 16:08