Hi there!

 

I am trying to calculate the complexity of an algorithm and I have concluded that it takes a number of steps given by the following formula (in Mathematica notation):

 

Hypergeometric1F1(-D, 2, -x)

 

This looks like a multinomial of x. The order of this polynomial is D. The last term of this polynomial is x^D/D!, which converges to 0 when D is large enough. On the contrary, the first terms seem to be significant.

 

Do you have any suggestions for the complexity of the algorithm? Is it polynomial or exponential with respect to D?

 

Thanks in advance!

What is D ?

If D > 0 and if D is an integer indeed the series will terminate and your hypergeometric function will be a polynomial.

What do you mean with x^D/D! converges to zero ? (You should at least keep x fixed in such an argument).

 

Anyway the way you write down the hypergeometric function the D! will be in the upperpart of the fraction, so you have more something like D! x^D then x^D/D!

 

A quick maple calculation shows that hypergeom(-D;2:-x) behaves like :

1 + 1/2 D x + 1/12 D (D - 1) x^2 + 1/144 D (D - 1) (D - 2) x^3 + 1/2880 D (D - 1) (D - 2) (D - 3) x^4 + 1/86400 D (D - 1) (D - 2) (D - 3) (D - 4) x^5 + 1/3628800 D (D - 1) (D - 2) (D - 3) (D - 4) (D - 5) x^6 + 1/203212800 D (D - 1) (D - 2) (D - 3) (D - 4) (D - 5) (D - 6) x^7 + 1/14631321600 D (D - 1) (D - 2) (D - 3) (D - 4) (D - 5) (D - 6) (D - 7)x^8 + 1/1316818944000 D (D - 1) (D - 2) (D - 3) (D - 4) (D - 5) (D - 6) (D - 7) (D - 8) x ^9 + O(x^10)

 

Your algorithm looks more factorial than anything else i think.

 

Mandrake

My mistake... I should have given you more information. In my case, D is the number of dimensions of my problem. So, consider D as a positive integer variable. As D increases, my problem becomes harder to solve. What I am searching for is how much harder it becomes.

 

In your maple representation the factor of the last term is

 

(D!) / (D!)^2 =

= 1/(D!)

 

This is the reason why I said that the last term is:

 

(x^D) / (D!)

 

D! increases faster than x^D, as D becomes larger. So, in my opinion,

 

(x^D) / (D!) -> 0

 

But then, which term of the multinomial is the greatest? What is the order of this multinomial? And finally, what is the complexity of the algorithm?

 

I hope that everything is more clear now. I am expecting for further suggestions.

What is x then ?

Does it depend on D is some way ?

(If x(D) = D! then your above limit argument is flawed).

 

Mandrake

No. x does not depend on D. You can consider it as a constant. D is my variable.

You still didnt say what is x. But your algorithm is exponential in the size of your problem instance D. (since you have a lot of terms of the type x^(something with D), like D, D - 1 etc...

The bigger D, the more terms you have. The only reason in the last term X^D, you have something like x^D/D! is because you have D! x^n/n!^2 for n =D, so maybe you can estimate the terms before ?

Something like the coefficient of the n-1ste term behave at least like .... (something with n) and at most like (something with n), that way you know how your function behave approximately and you can send n to infinity and maybe use some of the assymptotic formula for hypergeometric fucntions. (Remember that they are each a solution to some differential equation).

 

Mandrake