Time complexity of quadratic programming

Question

I am using the Matlab built-in quadprog to solve a quadratic program with linear constraints. I vaguely recalled from school that the time complexity of quadratic programming should be $O(n^3)$, and I assume n refers to the number of decision variables. However, when I experimentally compute the execution time as a function of the number of variables in Matlab, the execution time actually increases less than linearly with more variables. Increasing the number of variables from 10 to 100 only increases the execution time by 5 times. I am very puzzled by this result and perhaps what I remembered is wrong. Can anyone shed some light on the time complexity of quadratic program in theory and in practice?

Answer 1

I am not familiar with the details of the quadprog function, but I think the issues may be more universal. The cubic time complexity is an asymptotic worst-case bound. It does not mean that growing any problem by 10 times will increase running time by 1000 times. It will often be less, but may be that bad for some problem data.

There is often constant time "overhead" for many algorithms. The overhead may be so large that the running time is essentially independent of the problem size up to a certain point. The asymptotic bound only becomes relevant when comparing large problems with very large problems. In your example this will be hard to observe because quadratic programs with thousands or tens of thousands of variables can take hours or days to solve on a typical personal computer. Memory can become an issue since the problem data alone grows quadratically in the number of variables.

There is a whole industry devoted to these issues. Commercial solvers can cost tens of thousands of dollars. For specific applications, specialized solvers that exploit problem structure are often utilized. Sparsity of the input matrices is the most basic source of running time improvements.

Asymptotic worst-case bounds are often a poor guide for practical problem solving. They are certainly hard to verify using simulations. I suggest you move over to stackexchange for messy, detailed discussions of particular software implementations of algorithms.