Re: [Bug-gsl] Slow gsl_permutation_valid()

[Brian Gough]

Rajeev Ayyagari writes:
 > This is a suggestion rather than a bug report. The function
 > gsl_permutation_valid() in the current version (1.4) takes \Theta(1)
 > memory and runs in \Theta(n^2) time (where n is the size of the
 > permutation). It could be rewritten to use \Theta(n) memory and run in
 > \Theta(n) time. The time savings can be very significant if n is large (n
 > > 2000).

Hi,

Thanks for the suggestion.  The reason the library version is O(n^2)
is because in gsl we generally avoid dynamic allocation of memory
inside functions (it is difficult to recover from an error in that
case).  

Of course, if you need to use that function frequently you could
substitute the faster version in your application (e.g. via a macro).

best regards,

-- 
Brian Gough