I was asked to move the question here (https://stackoverflow.com/questions/72692849/check-if-growth-rate-is-worse-than-quadratic)
Let's say I have collected a dataset for estimating algorithmic complexity:
where x is the input size and t is the elapsed time. This may be
O(1), O(logn), O(n), O(n^2), O(n^3) etc.. To find the closest class, it would be necessary to run a linear/non-linear regression to fit the data and find the curve of the best fit. However, that would be too time consuming.
My question is: is there a quick way to tell if the rate of growth is worse than O(n^2)?
One of the answers over there said this which I find enlightening:
You can perform linear regression log(x) against log(t). If it is log(x) = a + b log(t), then x = O(t^b). If b is statistically greater than 2, then your assumption about complexity worse than O(x^2) holds.