I have a problem which essentially reduces to this:
- You have a black-box function that accepts inputs of length $n$.
- You can measure the amount of time the function takes to return the answer, but you can't see exactly how it was calculated.
- 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)