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.

Improve this question
$\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

Reset to default

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.