Evaluating time complexity for the binomial coefficient

user_5379913 0
Viewed 334

I'm new to Theoretical Computer Science, and I would like to calculate the time complexity of the following algorithm that evaluates the binomial coefficient defined as

$\left(\begin{array}{l}n \ k\end{array}\right)=\frac{n !}{k !(n-k) !}$

nf = 1; 
for i = 2 to n do nf = nf * i; 
kf = 1; 
for i = 2 to k do kf = kf * i; 
nkf = 1; 
for i = 2 to n-k do nkf = nkf * i; 
c = nf / (kf * nkf);

My textbook suggests to use Stirling's approximation

$n ! \approx \sqrt{2 \pi n}\left(\frac{n}{e}\right)^{n}$.

However, I can get the same result by considering that for i = 2 to n do nf = nf * i; have complexity O(n-2)=O(n), that is predominant.

Stirling's approximation seems a little bit overkill. Is my approach wrong?

complexity-theory time-complexity
1 Answers

In your first approach you calculate n!, k! and (n-k)! separately and then calculate the binomial coefficient. Therefore since all of those terms can be calculated with at most operations you have O(n) time complexity.

However, you are wrong about the time complexity of calculating the Stirling's formula. You only need log(n) in base 2 operations to calculate it. This is because when trying to calculate p'th power of some real number, instead of multiplicating it p times, you can instead keep squaring the number to calculate it quickly. For example:

If you want to calculate 2^17, instead of doing 17 operations like this:

return 2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2

you can do this:

a = 2*2
b = a*a
c = b*b
d = c*c
return d * 2

which is only 5 operations.

Note: However keep in mind that the Stirling's formula is not equal to the factorial. It is only an approximation but a good one.

Edit: Also you can consider a^n as e^(log(a)*n) and then calculate it by the quickly converging series expansion

1 + (log(a)n) + ((log(a)n)^2)/2! + ((log(a)n)^3)/3! + ...

Since the series converges very quickly you can get really close approximations in no time.

user_60870870
Related