in Algorithms recategorized by
175 views
1 vote
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

  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
in Algorithms recategorized by
by
175 views

1 comment

@Sachin Mittal 1 sir pls provide solution for this question

0
0

Please log in or register to answer this question.

Answer:

Related questions