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

  • $\begingroup$ 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? $\endgroup$
    – Nin17
    Jun 20 at 20:55
  • 3
    $\begingroup$ 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. $\endgroup$
    – SUTerliakov
    Jun 20 at 20:58
  • $\begingroup$ @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. $\endgroup$
    – Ricky Han
    Jun 20 at 21:00
  • $\begingroup$ @SUTerliakov that's a good idea. Thanks! I will try it out. $\endgroup$
    – Ricky Han
    Jun 20 at 21:02
  • $\begingroup$ @Nin17 I think this won't work because of lower order coefficients $\endgroup$
    – Ricky Han
    Jun 20 at 21:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.