[Solved]: How to determine if a black-box is polynomial or exponential

Problem Detail: 

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)

Asked By : stevenheidel

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23686