1
$\begingroup$

I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of instances, which grow in size as a function of $n$.

Now, I have collected running times from $n = 1$ up to $n = 5000$, which is as far as my computer can go in a reasonable amount of time.

I have plotted my data using Python and I have made some simple regression (exponential, cuadratic, cubic...), but I still can't get to decide which function best fits the algorithm. Obviously, if I try regression with a polynomial of higher degree, I will get a tighter curve, so in case the running time is a polynomial in $n$, I don't know how I could decide which is the one that really fits.

With instances up to $n = 1000$, it seems like the cubic polynomial is the best approximation. However, when I plot the instances up to $n = 5000$, things become less clear (in the second graph I compare the actual running times against the approximations obtained for up to $n =1000$, while the first one compares against the the approximations up to $n = 500$)

enter image description here enter image description here

(in addition, I feel there is something off with float point calculations, as two of the curves below get really messy)

Any suggestions?

A bit of context: I am working on a particular class of hard Quantified Boolean Formulas (QBF) and I want to test their running times on different available QBF-solvers. These formulas verify a certain interesting property: they have linear size proofs in the QU-resolution proof system. However, QBF-solvers act as block boxes for me, and, altough I can see from data that they do not have the "predicted" linear running times, I would like to know how is the growth in complexity in these particular instances. Particularly, it would be great to give some approximate bound or even confirm that they do not seem to have an exponential growth. Thanks.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ In general, you cannot obtain asymptotic complexity from only testing, see e.g. How to fool the plot inspection heuristic. The question then of course remains what you can meaningfully say about (a statistical analysis of) the results of your test. But that the depends on the use-case. Could you clarify what you'd want to use the complexity of the algorithm for? $\endgroup$
    – Discrete lizard ♦
    Commented Jul 23, 2019 at 8:19
  • $\begingroup$ @Discretelizard I just added some context to my post. Thanks for the link; I have been doing some research and I see now that, in general, it is complicated if not almost impossible to extract asympotic complexity from running times. Still, it would be great if I could conclude something more meaningful from my statistical analysis, as you mention. $\endgroup$
    – Noel Arteche
    Commented Jul 23, 2019 at 9:58
  • $\begingroup$ I must say your plots look nothing like what I would expect a regression to look like. $\endgroup$
    – gnasher729
    Commented Jul 23, 2019 at 10:17

1 Answer 1

Reset to default
-1
$\begingroup$

You can do regression on the whole data to get a better fit.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ We're looking for more detail than this in answers. $\endgroup$
    – David Richerby
    Commented Jul 23, 2019 at 9:31
  • $\begingroup$ Hmm ok. Not really sure what else to say for this particular problem. $\endgroup$
    – Dmitry Kamenetsky
    Commented Jul 23, 2019 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.