Identifying algorithms' running time from their curves

Question

I need to identify which of the curves $A_1,...,A_5$ are related to algorithms whose run times are proportional to $n, \log(n), n^2, n^3$ and $1.1^n$:

(Mentioning that the first figure of the $A_5$ column should be $0.015$ (not $0.025$)

Answer 1

It can be done at sight I think, but you can try to adjust each function to each curve and pick the one that minimize the error using minimum square deviation. Let's say you want to check if curve A1 is proportional to $f(n)=n^2$. You try to minimize the function $g(a,b)=\Sigma(a f(x_i) + b - y_i)^2$ Here $x_i$ is the size of the input and $y_i$ is the time it takes.

Answer 2

As Marcelo suggest, you can identify some of the curves if not all at sight.

linear

$A_4$ is a straight line, so this is a linear algorithm in $\Theta(n)$.

log

$A_2$ is concave, so among the suggested algorithms, only the logarithm fits $\Theta(\log(n))$.

exponential

Now it remains only $n^2,n^3$ and $1.1^n$, for $A_3,A_4,A_5$ this is not easy to distinguish them by sight.

But from the array, you can divide consecutive terms, and hopefully the exponential $\frac{C\mu^{n}}{C\mu^{n-5}}=\mu^5$ will emerge naturally.

And effectively when you do this you find that $A_3$ fits the model $\mu^5\simeq 1.6\iff \mu\simeq 1.1$ so $A_3$ appear to be $\Theta(1.1^n)$

polynomial

It remains the two blue curves $A_1$ and $A_5$. From the graphic you can notice that $A_5$ is catching up on $A_1$ so $A_1$ should be $\Theta(n^2)$ and $A_5$ should be $\Theta(n^3)$.

To help further identification you can also convert your data to $\log$ scale (this is $\ln(n)$ abscissa), and now if you trace the curves, they are straight lines.

You can measure the slope gradient $\alpha$ and the equation is : $ln(a(n))=\alpha\ln(n)+\beta$.

But this is equivalent in the normal scale to $a(n)=e^{\beta}n^\alpha=Cn^\alpha$ with a constant $C$.