MCQs about Time and Space Complexity Of a Program

tutorial
41

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

42

Anyone can explain 13th?

43 
def f():
	ans = 0
	for (i = n; i >= 1; i /= 2):  // 1         
		for j = m to i:       //2
			ans += (i * j)   
	print(ans)
  1. 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

  1. 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 :slight_smile:

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

8 Likes
44

Thnx, great first answer!! :smiley:

1 Like
45

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

1 Like
46

Hi, taran_1407 I think 9th question answer is A. Because inner loop not executed
how to possible j=n and j<i

47

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

1 Like
48

Cant figure out the19th question…PLease help!!!

49

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

1 Like
50

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–)

51

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.

52

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

53

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).

54

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

1 Like
55

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

56

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

57

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

58

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

59

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 C
18 D
19 B
20 B
21 C

1 Like
60

If codes are written in Python, then there is something wrong with Q11. It will run forever because n never will be 0 or negative. I think division should be replaced with floor division in the Q11:

def f(n):
	ans = 0
	while (n > 0):
		ans += n
		n //= 2;
	print(ans)

Edit: It’s also the case with Q12.