1

I have data (running time $T$ and problem size $N$). If I suspect that there is a polynomial relationship in the form $T=a N^b$, I can plot a log-log graph and work out the gradient, as stated on the wikipedia article: https://en.wikipedia.org/wiki/Log%E2%80%93log_plot

If I suspect that it has an exponential relationship, I can plot a semi-log graph: https://en.wikipedia.org/wiki/Semi-log_plot

What if I suspect that $T$ and $N$ has logarithmic relationship, $T=log(N)$, what can I use to show this?

What can I do for factorial complexity?

I asked a similar question here: https://math.stackexchange.com/questions/1596617/determine-complexity

But now I'm more interested in finding out how can I estimate different classes of complexity with just experimental data (where the algorithm is possibly too complex to analyse).

Community
  • 1
datguyray
  • 33

1 Answers1

1

If $T = \log N, N=e^T$ or whatever base of logs you are using, so you can plot on semi-log paper the same way in the reverse sense.

For the more general question, if you have data over a wide enough range it will be obvious. Logs grow very slowly, polynomials faster, exponentials faster yet. Factorials are faster than exponentials, but not much. If you are comparing $1.0000001^n$ with a polynomial it might be hard, but $2^n$ outstrips any reasonable polynomial (say $x^6$) by the time $n=30$

Ross Millikan
  • 374,822
  • Good idea, but I don't know the base. Would there be a way to work out the base given just the experimental data? – datguyray Jan 02 '16 at 03:21
  • Complexity theorists generally don't care about the base, as it is a constant that can be dropped. – ml0105 Jan 02 '16 at 03:25
  • You used the log, so you should know the base. It doesn't really matter much-my example with $2$ shows what happens there. If the base is $10$ it grows much faster. In theory, a polynomial could be $x^{1,000,000}$, and it would take a long time for $2^x$ to outrun it, but we don't see polynomials with that high a degree. The statement that any exponential (with a base greater than $1$) eventually outstrips any polynomial is correct, but it can take a long time. In reasonable cases the degree is low, the base of the exponential is not so close to $1$ so it doesn't take so long. – Ross Millikan Jan 02 '16 at 03:27