1.B

2.C

3.B

4.B

5.C

6.D

7.C

8.C

9.C

10.B

11.A

12.C

13.C

14.B

15.B

16.B

17.B

18.D

19.B

20.B

21.C

# Multiple Choice Questions Related To Testing Knowledge about Time and Space Complexity Of A Program

Anyone can explain 13th?

```
def f():
ans = 0
for (i = n; i >= 1; i /= 2): // 1
for j = m to i: //2
ans += (i * j)
print(ans)
```

- loops of this kind runs for log(n) time.

How? You can take example.

n=1 => log2(1) = 0

n=2 => log2(2) = 1

n=4 => log2(4) = 2

… Here n follows pattern.

When n is multiplied by 2 at each step(Which is opposite case than the described case)

In given case **i** starts from some value **n**.

In next loop execution i= n/2

… i=n/4

…

…i=n/(2^k) (last execution step of loop)

When i is 1 => n=2^k => k=log(n)

Those are total steps to be computed for each execution.(You can start from k=0 and so on to get value of i for each execution)

You can shortlist options according to which option has log(n). Only one option has log(n) in options so that’s the **answer C**

- It is not specified if value of m is greater than n or not. So we keep m as it is. And we will take modulus at last as we are using subtraction.

Step 1 : i=n

Executions of statement : (n-m) times

Step 2 : i=n/2

Execution of statement : (n/2 - m) times

Step 3 : i=n/4

Execution of statement : (n/4 - m) times

…

Step k: i=1 (Where n/(n^k) = 1 =>k=log(n) )

Execution of statement : (1 - m) times

To find total executions we take sum of all above step executions

|( n + n/2 + n/4 + … + 1) - m*k |

Replace k by log(n), and taking n common in first bracket

**|n(1 + 1/2 + 1/4 + 1/8 …) - m*log(n)|**

We can observe that constant term will approach 2 for large value of n.

And **x*log(y)** has higher priority than **z** when both terms are present.

So removing first term what we get is : **m*log(n)** a.k.a. **option C**

Please **Upvote** it helped. It was my **first answer** so sorry if there are any typos or mistakes

Reference : Link to Youtube video and playlist by Mr. Abdul Bari

Thnx, great first answer!!

log(n!)<=nlog(n) i.e. log(n!)=O(nlog(n))

Hi, taran_1407 I think 9th question answer is A. Because inner loop not executed

how to possible j=n and j<i

@admin please help in 17th question what happen if all a element are x then time complexity of programme

Cant figure out the19th question…PLease help!!!

Can someone please explain the solution of Q6,13,14,15,18,20.

Bro it’s pseudo code, if it’s written for j=n to i, it means loop starts from n and decrease value of j till i, more formally it would be same as for(int j=n;j>i;j–)

It’s about finding the first n Fibonacci numbers with memoization( in simple words, DP(Dynamics programming). Google it and read the tutorials to know more about what is dp.

1-c

2-c

3-b

4-b

5-c

6-d

7-c

8-?

9-c

10-b

11-a

12-c

13-c

14-b

15-b

16-?

17-?

18-b

19-?

20-?

21-d

I think

in question no 5 time complexity depend upon the value of “m” and “n” if(m>n) then time complexity is O(m) else O(n).

1 B

2 C

3 B

4 B

5 C

6 D

7 C

8 C

9 C

10 B

11 A

12 C

13 C

14 B

15 B

16 B

17 B

18 D

19 B

20 B

21 C

I WAS TOTALLY BLANK AT QUESTION NO 15 CAN ANYONE EXPLAIN THAT PLEASE ???

In Q12, won’t all of the first three options be true because of O(log_2 n) = O(log_{10} n)?

1.B

2.C

3.B

4.B

5.C

6. C

7. C

8. C

9.A

10.B

11.B

12.C

13.B

14.A

15.C

16. B

17. B

18.B

19.B

20. B

21. D

1)B

2)C

3)B

4)B

5)C

6)D

7)C

8)C

9)C

10)B

11)A

12)C

13)C

14)B

15)B

16) B

17)B

18)D

19) B

20)B

21)C