This question is probably stupid, but I’ve been trying to figure this out for hours and I still couldn’t find anything about it. Probably I’m just too lost.
So basically, I’m analysing an algorithm by doing an asymptotic and experimental analysis. The asymptotic analysis went well and I concluded that my algorithm is O(nlogn). The problem is the experimental analysis. Firstly, I did some tests to get the time taken for each input. For example:
n = 1, t = 0 | n = 2, t = 2 | n = 4, t = 8 | n = 8, t = 24 | n = 16, t = 64 | n = 32, t = 160 (…)
If I do the graph with this example, I can see that it is an O(n log n)/linearithmetic graph, but how do I prove it? Do I have to calculate the order of growth? If so, how do I do it?
Thanks for the help!
Plot the time against the input size.
Curve fit a
y=A*n*log(n) + B curve to that plot, solving for A and B by creating a least means square fit of the realtionship between this curve and the experimental plotting.
Perform the same for a linear curve (a line) which represents
O(n) and for
O(n^2). Show that the fit of the other curves has more error has more error than the
If the error of the one curve’s fit is lower, the data you collected supports that it is growing at the big-O notation for that curve.