For each element of the table we must perform one matrix addition, two matrix multiplications, and one matrix inverse on the matrices from the PFA, which has overall time complexity O(|Q| m ).
the runtime of Algorithm 2 is O(|w|(|w| 2 |Q| m )) = O(|w| 3 |Q| m ), where m is the matrix multiplication constant.