236 views

Consider the following algorithm for computing the factorial of a positive integer $n$, specified in binary:

prod ← 1
for i from 1 to n
prod ← prod × i
output prod

Assume that the number of bit operations required to multiply a $k$-bit positive integer with an $\ell$-bit positive integer is at least $\Omega(k+l)$ and at most $O(kl)$. Then, the number of bit operations required by this algorithm is

1. $O(n)$
2. $O(n \log n)$ but $\omega(n)$
3. $O\left(n^2\right)$ but $\omega(n \log n)$
4. $O\left(n^3\right)$ but $\omega\left(n^2\right)$
5. None of the above

### 1 comment

@Sachin Mittal 1 sir pls provide solution for this question

1 vote