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
