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

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)

• 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. – Raphael Apr 12 '14 at 7:44

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.
• @Kaveh I don't think so; if $t = n^c$ then $\log t/\log n = c$. – Yuval Filmus Apr 26 '14 at 23:21