# Multiple Choice Questions Related To Testing Knowledge about Time and Space Complexity Of A Program

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

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

1 Like

Really?
I guessed 2nd and 15th.

yes, they are right too.

@akash_321: Yes, you are right. It will be \mathcal{O}(n).

1 Like

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

1 Like

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

2 Likes

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

Just remember to set correct upper limit

Yes, surely i will. @vijju123

1 Like

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.

1 Like

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.

1 Like

Can anyone explain Q20…?