MCQs about Time and Space Complexity Of a Program

tutorial
4

In question 17 if all elements of a are x wouldn’t the complexity be O(n).
@taran_1407 @admin @vijju123 anyone?

7 Likes
5

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 a

1 Like
6

Please explain the soln. for Q.20.

5 Likes
7

Question 13:

If n is large, and m is small, then the innermost statement is executed n + n/2 + n/4 + \ldots times.
So the problem is at least {\scr O}(n).

If n and m are large, then the innermost statement is executed roughly m \log n times.

So I believe the problem as a whole is {\scr O}(n+m\log n).

The only choice available that is big enough is B: {\scr O}(n \times m).

Question 21:

Has no options C, and two options D. The correct choice is the first option D!

6 Likes
8

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

1 Like
9

q12 Theoretically , A,B,C are all correct

10

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)

12 Likes
11

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

12

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

2 Likes
13

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

1 Like
14

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.

6 Likes
15

Please explain me 21st question’s solution.

16

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

4 Likes
17

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

18

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

4 Likes
19

can anyone explain problem 6 and 18

20

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

21

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

22

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
23

kudos, I think all your answers are correct :slight_smile: