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!
Advertisement
Answer
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 O(n*log(n)) curve.
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.