MCQs about Time and Space Complexity Of a Program

tutorial
28

So if number of occurrences of x are m then complexity will be O(m).

1 Like
29

Yes. The main focus was, it takes O(LogN) time to find ocurrances of x in the sorted array. I think this question goes by an assumption that “Number of occurances of x very less than Number of elements in array.”

3 Likes
30

Yes, You are absolutely right @akash_321, Though there exist a better way to count number of occurance of an element in a sorted array in O(logN) time.

1 Like
31

Just remember to set correct upper limit :stuck_out_tongue:

32

Yes, surely i will. :smiley: @vijju123

1 Like
33

j does not get re-initialized every step. Its initialized to 0 only once, and remembers the value of previous iteration. So, once it reaches n, inner loop will never execute. Hence the algo will execute maximum 2n times.

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