4
$\begingroup$

This is my first question here. I'm not a CS at all, so it might be quite trivial.

I have written a program in C where I allocate memory to store a matrix of dimensions n-by-n and then feed a linear algebra subroutine with. I'm having big troubles in understanding how to identify time complexity for these operations from a plot. Particularly, I'm interested in identify how CPU time scales as a function of n, where n is my size.

To do so, I created an array of n = 2, 4, 8, ..., 512 and I computed the CPU time for both the operations. I repeated this process 10000 times for each n and I took the mean eventually. I therefore come up with a second array that I can match with my array of n.

I've been suggested to print in double logarithmic plot, and I read in Wolfram that, using this way, "powers shows up as a straight line". This is the resulting figure (dgesv is the linear algebra subroutine I used).

double logarithmic plot

Now, I'm guessing that my time complexity is $O(a^n)$ since I get straight lines for both my operations (I do not take into consideration the red line). I saw the shapes differences between, say, linear complexity, logarithmic complexity etc. But I still have doubts if I should say something about the time complexity of dgesv, for instance. I'm sure there's a way that I don't know at all, so I'd be glad if someone could help me in understanding how to look at this plot properly.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Since these are ms, the plot is too small to make any valid assumption. If the plot is bigger to get execution time into seconds, then reading the complexity from the plot is a bad idea. Besides cache, memory considerations it is not asymptotic yet, just a bigger sample to show behaviour. There is no need for 10000 repeats, but if you could please use trimmed (or Windsorized) mean or median to really discard outliers. $\endgroup$ – Evil Nov 23 '16 at 21:35
  • $\begingroup$ @Evil thanks for the suggestions. So, just to see if I've understood correctly: should I get some bigger time in ms to make any valid assumption, or is it just a bad idea at all? $\endgroup$ – Mattia Paterna Nov 23 '16 at 21:44
  • 2
    $\begingroup$ Related (but different): cs.stackexchange.com/q/48505/755 and cs.stackexchange.com/q/857/755. $\endgroup$ – D.W.♦ Nov 23 '16 at 22:15
  • 1
    $\begingroup$ Please read the both links from D.W., and decide yourself. The asymptotic complexity read from small sample may fail. I encourage something more roboust than simple mean, longer times (meaning bigger input) to make any temporal fluctuations neglible. Then you could state how it behaves and read the approximation of complexity - just use it with caution, as the plot may get some reflection point further so asymptotically the other one may be faster. For fixed or bounded calculations reading the plot is ok. $\endgroup$ – Evil Nov 23 '16 at 22:31
1
$\begingroup$

No, you can't prove asymptotic properties from finite samples. See here and here for more on this.

Plots can give you hints towards the real properties of the running-time function, though, which you can then go ahead and try to prove.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.