# Time complexity of quadratic programming

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?

-
 Pretty sure that quadprog sometimes defaults to simplex-like active set methods for small problem sizes. Those algorithms are absolutely infamous for having a huge gap between theoretical complexity and actual observed runtime. It's like a dirty secret from Computer Science that is underexposed. – Peter Sheldrick Nov 23 '12 at 1:00 Better bounds for the complexity the simplex algorithm was for example what the recent Hirsch conjecture media blitz was about. – Peter Sheldrick Nov 23 '12 at 1:07