# 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)?

• why would you need to fit every curve possible? / too many curves? why can't you just fit one curve and see what order polynomial it is?
– Nin17
Jun 20 at 20:55
• 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.
– SUTerliakov
Jun 20 at 20:58
• @Nin17 I just need to know if it's worse than polynomial. Fitting one curve is risky because for example quadratic curve with big coefficients can approximate a linear growth rate quiet well. Jun 20 at 21:00
• @SUTerliakov that's a good idea. Thanks! I will try it out. Jun 20 at 21:02
• @Nin17 I think this won't work because of lower order coefficients Jun 20 at 21:03