# Check if growth rate is worse than quadratic?

Let's say I have collected a dataset for estimating algorithmic complexity:

x t
1 1
2 4
3 9
4 16

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.

• Graphically, the question would be whether the curve on a log-log scale appeared to approach a limiting straight line, and whether the limiting slope was greater than 2. How many data points do you actually have, over what scale? Only 4, or is that just a simplified example? Jun 21 at 2:11
• The advice is reasonable, but it could fail when the function has lower-order additive components and $n$ is not large enough to make them negligible. Worthy of consideration is the nature of the error: when repeating the algorithm for a given $n,$ exactly how much variation is expected in the timing? A log-log plot of the data is worth more than any test or regression model in this regard.
– whuber
Jun 21 at 2:27
• This test is only executes when there are enough data points. I have tested log-log plot against an example quadratic algorithm. The variations for different $n$ are large and well-behaved. Thank you for the solution! Jun 21 at 4:50