Solution Found!
Consider the problem of computing N! = 1 2 3 N.(a) If N is an n-bit number, how many
Chapter 1, Problem 1.31(choose chapter or problem)
QUESTION:
Consider the problem of computing \(N !=1 \cdot 2 \cdot 3 \cdots N\).
(a) If N is an n-bit number, how many bits long is N!, approximately (in \(\Theta(\cdot)\) form)?
(b) Give an algorithm to compute N! and analyze its running time.
Questions & Answers
QUESTION:
Consider the problem of computing \(N !=1 \cdot 2 \cdot 3 \cdots N\).
(a) If N is an n-bit number, how many bits long is N!, approximately (in \(\Theta(\cdot)\) form)?
(b) Give an algorithm to compute N! and analyze its running time.
ANSWER:Step 1 of 5
a)
Note that the result of the factorial is
Since is bits long,
Also, if , then has bits.
Finally, the product of two numbers that have and bits is a number that has bits.