On the complexity of linear quadratic control

This paper presents an analysis of the computational complexity of the linear quadratic control models commonly used in Economics. These models differ in the statistical assumptions concerning the coefficients. The most common assumptions are fixed unknown, fixed known and independent random. A fourth model to be considered in the MacRae approximation. These four models have a nested structure. The computational complexity of the first is transfinite. The computational complexity of the second is linear in the time horizon, T and has the same computational complexity in the number of states, n as that for matrix multiplication of (n×n)-matrices. The computational complexity of the third is n⁴T. The computational complexity of each iteration of the MacRae approximation is n⁴T.