1 B

2 C

3 B

4 B

5 C

6 D

7 C

8 D

9 C

Three Loops are there so for single loop complexity will be “n” for three loop complexity will be “n^3”

10 B

11 A

12 C

13 C

14 B

15 C

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

As both n and m are the input parameters of the function. So, we should give \mathcal{O}(n + m) as time complexity.

kudos, I think all your answers are correct

Really?

I guessed 2nd and 15th.

yes, they are right too.

Since counter increases by 1, of course, it is expected to be O(N) worst case.

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

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

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.

Just remember to set correct upper limit

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.

Since when we started assuming things, that too on codechef.

big O is always worst case complexity.

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

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

The explanation is correct 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.

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

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.

Can anyone explain Q20…?