Question

Consider the problem of computing N! = 1 2 3 N.

(a) If N is an n-bit number, how many bits long is N!, approximately (in () form)?

(b) Give an algorithm to compute N! and analyze its running time.

EXPERT ANSWER

#### Part a:

Using Stirling’s approximation to the factorial, N! is approximately equal to {eq}sqrt{(2 pi N) N^N/e^N}

{/eq}, so:

{eq}log_2(N!) log_2((2 pi N)^{1/2}N^N / e^N)

{/eq}

= {eq}(1 + log_2 pi + log_2 N)/2