Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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)

share|improve this question
    
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 at 7:44

2 Answers 2

up vote 12 down vote accepted

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.

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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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