Determinating Complexity time

Question

I'm doing a project for university about how to determinate Complexity assuming that all that is known about an algorithm are their running times depending on the data size.

The types of algorithm I use are polynomial (n2, n3,..,n6), logarithmic and exponential.

For example, an imput of the program it can be:

n 1 2 3 4 5 6 7 8 9 10 11 12 (data size)

T(n) 0,9 / 1,6 / 2,3 / 3,0 / 3,7 / 4,4 / 5,1 / 5,8 / 6,5 / 7,2 / 7,9 / 8,6

So, I've got an algorithm for the polynomial and logarithmic complexity, For now, the data is maximum 20

polynomial:

while answer = -1 and then j > 12 loop
aux:= true;
  for k in 1..j loop
    c := Polynomial(k+1);
    Polynomial(k) := Polynomial(k+1) - Polynomial(k);  
    aux:= aux and abs(Polynomial(k)) < abs (c * 0.005);  --Almost equal
  end loop;
   if aux then
     aux := 19 - j;
     end if;
   j := j-1;
end loop;

I've reached a dead end with the exponencial one. Could someone give me a hint? Thank you so much.

Answer 1

This sounds like a stochastic problem i.e. find the best model fit given a set of discrete points. The first thing I would do is determine the type: logarithmic/polynomial/exponential. To do that you can study the discrete derivative at each point. If the value of the first derivative is decreasing => logarithmic. To determine if it is polynomial or exponential again you should study the derivative, but this time not only the first order. The following can be observed: continues derivation of an exponential function is exponential as well while the polynomial one will get linear (derivative close to 0). Hence if after a couple of derivations your value are close to 0 => polynomial.

Having determined the type of the model you would now like to fit your points to that model. You can do it in C++ with the help of Eigen library and mainly their implementation of Levenberg–Marquardt algorithm