Question

Consider the problem of computing $\mathbf{N}\mathbf{!}\mathbf{=}\mathbf{1}\mathbf{·}\mathbf{2}\mathbf{·}\mathbf{3}\mathbf{·}\mathbf{·}\mathbf{·}\mathbf{N}$.

(a) If $\mathbf{N}$is an role="math" localid="1658397956489" ${\mathbf{n}}^{}$-bit number, how many bits long is $\mathbf{N}\mathbf{!}$, approximately ( $\mathbf{in\Theta }\mathbf{(}\mathbf{·}\mathbf{)}$form)?

(b) Give an algorithm to compute $\mathbf{N}\mathbf{!}$and analyze its running time.

Short answer

The running time complexity of the given algorithm can be analyzed as it runs for n iteration and that is multiplied and the final time complexity $\mathrm{O}\left(\mathrm{NlogN}\right)$.

Step-by-step solution

Introduction

The factorial can be defined as the product of all the numbers between 1 and the given number including the given number. It can be represented as an integer with an exclamation mark.

Calculation of bits long with N!

We have,

$\mathrm{N}!=1·2·3···\mathrm{N}.$

It is known that,

${\mathrm{Log}}_2(\mathrm{N}!)=\mathrm{\Theta }\left({\mathrm{Nlog}}_2\mathrm{N}\right)$

So, N-factorial can be written as,

$\mathrm{N}!=\mathrm{\Theta }\left({\mathrm{Nlog}}_2\mathrm{N}\right)$

It can be written as,$\mathrm{\Theta }\left(\mathrm{n}{2}^{\mathrm{n}}\right)$

Given that, N is a n-bit number, then

$\mathrm{N}!\mathrm{is}\mathrm{\Theta }\left(\mathrm{n}{2}^{\mathrm{n}}\right)\mathrm{bits}\mathrm{long}.$

Algorithm to compute N!

Normal algorithm flow is shown below,

$\begin{array}{l}\begin{array}{l}\mathrm{Factorial}\left(\mathrm{N}\right)\\ \mathrm{If}(\mathrm{N}==0)\\ \mathrm{Return}1\\ \mathrm{Else}\end{array}\\ \mathrm{Return}\mathrm{N}\mathrm{factorial}(\mathrm{N}-1)\end{array}$

The running time complexity of the given algorithm can be analyzing as it runs for n iteration and that are multiplied and the final time complexity $\mathrm{O}(\mathrm{N}\log \mathrm{N})$.