Estimate logarithmic complexity

146 Views Asked by At

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).

1

There are 1 best solutions below

3
On

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$