(Good points made by Bruno. This answer tries to dive a little more deeply than Bruno spent the time to do, but I really don't care if you just accept Bruno's answer, as it really did answer the heart of the question.)
To get a better answer as to how much time QR really takes requires much deeper investigation. And sometimes, there are incredibly strange interactions between various parts of your particular computer. There are several important things you need to do.
- Look at a larger set of array sizes
- Do not put the randn time into your time computation
- Use timeit, as a far better measure of the time taken than tic/toc
- Finally, plot AND model the results
I would do something like
N = [100:50:1000, 1100:100:2000, 2250:250:4000, 4500, 5000];
Now we would expect the resulting times to roughly follow a power model, of the form
T(N) = a + N^b
where b may be on the order of 3.
Note that if this is a perfect relationship, we would expect to see a straight line on that plot.
But what happens is for smaller matrix sizes, you have other factors in there. A huge part of it is just function call overhead, thus startup costs, error checking, etc. Those startup costs often take a virtually constant time. But that confuses things.
This suggests, using ALL of those times, that a reasonable model might have the QR time as O(N^2.5), at least based on my data. However, if we look only at the last 4 points from that curve, because there was a jog in the curve just below that...
p1 = 3.203 (2.823, 3.583)
p2 = -27.55 (-30.73, -24.37)
We see a time behavior as possibly closer to O(N^3.2). Since that uses only 4 data points, it might be a little suspect. And the exponent bounds clearly contain your hoped for value of 3.
Next, you might want to recognize those jogs in the curve. They are pretty significant. They may be subtle things induced by my own computer, how it uses memory, or interactions from the blas, or perhaps all sort of things I have not even considered. Some of those bumps might be where MATLAB suddenly decided to multi-thread the problem. My computer has 8 real cores.