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

Could someone please explain why the answer of question 21 is \mathcal{O}(n\log n)?

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

q12 Theoretically , A,B,C are all correct

Question 21 explained:

Here outer for loop (loop i) will run n times.
when i=1, inner loop (loop j) will run n/1 times [for j = 1; j <= n; j += 1]
when i=2, inner loop will run n/2 times [for j = 2; j <= n; j += 2]
…upto i=n, inner loop will run n/n=1 time [for j = n; j <= n; j += n]
So, Total time= O(n+ n/2+ n/3+ …+ n/n)
=O(n(1+1/2 +1/3+…+1/n))
=O(nlogn)

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

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.

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.C
19.B
20.B
21.A

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

Please explain question number 15 although i guessed it correct??

Q 15 anyone? Where can i see list of all different big oh complexity?

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.

Q17. Considering the worst case scenario if the whole array contains a duplicate entry, the algorithm has to go O(n) times to calculate the occurrence. According to me, it should be C.
Correct me if I’m wrong.

Please explain me 21st question’s solution.

I think Q.17th should have answer c) because we are considering worst case complexity here

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-C
20-D
21-C

Please someone explain Q.no 4?
according to me its log (n!)

can anyone explain problem 6 and 18

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 C
18 D
19 B
20 B
21 C

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