how to understand time complexity from a plot?

Question

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 here and here that, using this way, "powers shows up as a straight line" (2). This is the resulting figure (dgesv is the linear algebra subroutine I used).

Now, I'm guessing that my time complexity is O(log 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.

PS: if there's a specific community where to post this question, please let me know so I could move it avoiding much more mess here. Thanks everyone.

Answer 1

Take your yellow line, it appears to be going from (0.9, -2.6) to (2.7, 1.6), giving it a slope roughly equal to 2.5. As you're plotting log(t) versus log(n) this means that:

log(t) = 2.5 log(n) + c

or, exponentiating both sides:

t = exp(2.5 log(n) + c) = c' n^2.5

The power of 2.5 may be an underestimate as your dsegv likely has a cost of 2/3 n^3 (though O(n^2.5) is theoretically possible).