Multiple Choice Questions Related To Testing Knowledge 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


#44

Thnx, great first answer!! :smiley:


#45

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


#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