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).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.
how to understand time complexity from a plot?
algorithms;asymptotics;runtime analysis;experimental analysis
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.