@Sachin Mittal 1 sir pls provide solution for this question

Dark Mode

236 views

1 vote

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

- $O(n)$
- $O(n \log n)$ but $\omega(n)$
- $O\left(n^2\right)$ but $\omega(n \log n)$
- $O\left(n^3\right)$ but $\omega\left(n^2\right) $
- None of the above