3
$\begingroup$

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:

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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? $\endgroup$
    – Ben Bolker
    Jun 21 at 2:11
  • 2
    $\begingroup$ 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. $\endgroup$
    – whuber
    Jun 21 at 2:27
  • 1
    $\begingroup$ 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! $\endgroup$
    – Ricky Han
    Jun 21 at 4:50

0

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.