MCQs about Time and Space Complexity Of a Program

tutorial
34

Since when we started assuming things, that too on codechef. :slight_smile:
big O is always worst case complexity.

35

Check derivation of “Sieve ofErastothenes” . Its similar to that.

1 Like
36

Theoretically, yes. But the intent of the problem setter to check whether you understand the base of the logarithmic or not :wink:

37

The explanation is correct :slight_smile: But you can explain a bit about harmonic sum and then say that the harmonic sum is bounded by \log{n}, hence, we get an \mathcal{O}(n \log{n}) time algorithm.

38

I am curious as to how to know the complexity of a program, I have binged ( I don’t use google ) the answer, and I found it in several places( SO, wikipedia included ) and I never understand any of the explanation

39

it is n(1+1/2+1/3+1/4+…1/n). The sum in brackets converges to log(n) as n->inf. It is just a known mathematical result.

1 Like
40

Can anyone explain Q20…?

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