TIFR CSE 2022 | Part B | Question: 4

Question

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

• A. $O(n)$
• B. $O(n \log n)$ but $\omega(n)$
• C. $O\left(n^2\right)$ but $\omega(n \log n)$
• D. $O\left(n^3\right)$ but $\omega\left(n^2\right) $
• E. None of the above

Comments

@Sachin Mittal 1 sir pls provide solution for this question

Answer 1

n!=n*n-1*n-2*...*2*1.

Lets first calculate how many calculations needed to find n!

to find 1! 0 calculations

to find 2! = 2*1! = 1 calculations

to find 3! = 3*2! = 3*2*1! = 2 calculations

therefore for n! we need n-1 calculations.

total number of bit operation required = no of multiplication required x no of bit operations required in each multiplication.

Lets calculate no of bit operations required in each multiplication.

the bit operations will always be less then or equal to no of bit operations in (n-1)!xn

Lets find out number of bits in (n-1)!

(n-1)! = 1x2x3x...x(n-2)x(n-1)

if n is k bit integer then every other number must be atmost k bits. So number of bits in (n-1)! = k+k+...+k(n-1 times) = (n-1)k $\approx$ nk

Given that the number of bit operations required to multiply a k-bit positive integer with an l-bit positive integer is at least $\Omega$(k+l) and at most O(kl).

So no of bit operations in (n-1)! x n is $\leq$ no of bits in (n-1)! x n

=nk * k = nk$^{2}$

as n is k bit number so logn=k therefore n(logn)$^{2}$

therefore total number of bit operation required   $\leq$ n-1 x n(logn)$^{2}$ $\leq$  (nlogn)$^{2}$

no of bit operations in (n-1)! x n is $\geq$ nk + k$\geq$ nk

therefore total number of bit operation required $\geq$ (n-1) x nk $\geq$ n$^{2}$logn $\geq$ n$^{2}$

Hence answer is option D.