n!
---------
r!(n-r)!
and this is O(n3). as calculating each of the factorials is at least O(n)
The following is my new algorithm that saves memory and also running time written in C++:
long int choose(int n,int r){
//double ensures that precession is preserved
//when dividing as int rounds up the dividend in C++
double num,den,comb=1;
if (n == 0 || n == r){
return 1;
}else{
for (i=0; i<r || i<(n-r) ; i++){
num = double(n-i);
den = double(i+1);
comb *= num/den;
}
}
return comb;
}
This is O(n) because of the for loop.
2 comments:
Have you not forgotten increment part and terminating condition in the for loop? It seems to be an interesting algorithm: cutting from O(n3) to O(n). I really want to test it!
@Bennette
I did not forget the incremental part and the condition. I guess the Blogger Parse removed them somehow. Thanks for noticing it. I have had to twik it several times before making it dispaly them.
You may now test it.
Post a Comment