4
$\begingroup$

I have a problem which essentially reduces to this:

  1. You have a black-box function that accepts inputs of length $n$.
  2. You can measure the amount of time the function takes to return the answer, but you can't see exactly how it was calculated.
  3. You have to determine whether the time-complexity of this function is polynomial or exponential.

The way I did this was by running thousands of random sample inputs of varying lengths through the function, then plotting them on a scatter plot with times on the y-axis and input length on the x-axis.

What are some metrics and methods I can use to determine if these points best fit to a polynomial curve or to an exponential curve?

(Similar question asking how to draw polynomial/exponential best fit lines in Python on Stack Overflow: https://stackoverflow.com/questions/23026267/how-to-determine-if-a-black-box-is-polynomial-or-exponential)

|cite|improve this question
$\endgroup$
  • $\begingroup$ You can't, not with certainty: you may not even see the "true" behaviour in finite samples. Even with a white box, you can't. You can make educated guesses, though; see my answer on a related question. $\endgroup$ – Raphael♦ Apr 12 '14 at 7:44
12
$\begingroup$

Theoretically speaking, this is impossible to accomplish, basically because "polynomial" and "exponential" are asymptotic concepts, and no prefix of the data guarantees anything about the behavior at infinity.

Practically speaking, you can try to compute $t(n)^{1/n}$ and so if it approaches a constant bounded away from 1. If so, it is exponential. To test whether it's polynomial, you see whether $\log t/\log n$ approaches a constant. These are only rough tests, of course, but they could be useful in practice.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ shouldn't it be log t/n in place of log t/log n? $\endgroup$ – Kaveh Apr 26 '14 at 21:21
  • $\begingroup$ @Kaveh I don't think so; if $t = n^c$ then $\log t/\log n = c$. $\endgroup$ – Yuval Filmus Apr 26 '14 at 23:21
  • $\begingroup$ yes, sorry, I misread and thought it is for the exponential case. $\endgroup$ – Kaveh Apr 27 '14 at 3:55
1
$\begingroup$

Let's say your black box takes n^2 * 1.000001^n seconds to process input of size n. For n from 1 to 1,000,000 this is between n^2 and 2.718 n^2 seconds. Unfortunately, for n = 1,000,000 it will take about 80,000 years. So how are you going to find out that the time is exponential? On the other hand, since it takes 80,000 years anyway, do you care that it is exponential?

In practice, many algorithms have very non-smooth behaviour. For example, the naive algorithm for multiplying two n x n matrices of floating-point numbers does about n^3 multiplications and additions, but if you chart the time it takes on a current computer, that chart is all over the place.

|cite|improve this answer
$\endgroup$

Your Answer

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

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