How to determine if a black-box is polynomial or exponential

Question

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)

Answer 1

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.

Answer 2

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.