This paper proposes to use Nesterov's fast gradient method for the solution of linear quadratic model predictive control (MPC) problems with input constraints. The main focus is on the method's a priori computational complexity certification which consists of deriving lower iteration bounds such that a solution of pre-specified suboptimality is obtained for any possible state of the system. We investigate cold-and warm-starting strategies and provide an easily computable lower iteration bound for cold-starting and an asymptotic characterization of the bounds for warm-starting. Moreover, we characterize the set of MPC problems for which small iteration bounds and thus short solution times are expected. The theoretical findings and the practical relevance of the obtained lower iteration bounds are underpinned by various numerical examples and compared to certification results for a primal-dual interior point method.