MCQs about Time and Space Complexity Of a Program

tutorial
82

Hey Guys, I am a beginner please let me know if my answers are right?
Thanks

  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 (Guess)
  21. c
83

A1. B.
A2. C.
A3. B.
A4. B.
A5. C.
A6. D.
A7. C.
A8. C.
A9. C.
A10. B.
A11. A.
A12. C.
A13. C.
A14. B.
A15. C.
A16. B.
A17. B.
A18. D.
A19. B.
A20. D.
A21. C.

I am facing difficulty in understanding the solution to Question 15 and 20… Help will be much appreciated…

1 Like
84

can you please give explanation for the 11 th question

87

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 not confirm
16 B
17 B
18 D
19 B
20 B
21 D

88

J is increased only once then j will be n for all the other value of i

89

Thanks for helping with Q20…

1 Like
90

Q 20. It a tricky question so let me explain:
If you see the while loop the condition is and a[i] < a[j] and both i and j are starting from 0.
so for i = 0 and j = 0 it will not satisfied the condition
for i = 1 and j = 0 it will satisfied the condition and j will be update to j += 1 = 1 and condition will break and so on.
So the while loop will not iterate more than one time for any i and j.

Hope, I’ve explained it.

3 Likes
91

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

92

a

93

could anyone explain nlogn complexity ?

94

n[1+1/2 + 1/3 +… + 1/n]=n*infinity

95

1.B
2.C
3.B(if we consider average ) else D .
Which will be more correct ? Plz explain .
4.B
5.C
6.D
7.C
8.C
9.C
10.B
11.A
12.C
13.C
14.B
15.A (Doubt )
16.B
17.B
18.D
19.B
20.B
21.D(Doubt)
@admin Could you please explain me 15th

96

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

*not sure

97

For Q.17 I think the time complexity is O(n) because if the array contains all same numbers it has to check each and every number so it will be O(n).
Am I correct?

98

Can someone please tell me how to solve question 12?

99

Complexity should be log210 because loop will run for count of digits in a number times which is floor(log210)+1

100

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 need help
16 B
17 B
18 help
19 help
20 B
21 C
[/quote]

101

According to me
15-b
18-d
19-b
For 15 read about Euclidean Geometry Program to Find GCD or HCF of Two Numbers - GeeksforGeeks
For 18, each fun(n) is calling fun(n-1) and fun(n-2). So,each value is called twice. So, O(2^n).
When memoization is done we don’t need to call again and again. If we have stored value then we can directly access it . So, O(n).
algorithm analysis - Finding the time complexity of fibonacci sequence - Computer Science Stack Exchange
For more accurate see this Time complexity of recursive Fibonacci program - GeeksforGeeks

102

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

103

Hi,
Please correct me if i am wrong, but its like this.

for i = 1 - no. of times statement will run is log(1)
for i = 2 - no of times - log(1) + log(2)
Similarly, for n times - log(1) + log(2) + … log(n)
Now for all of the log function complexity is O(log n) so it will be same in n times
so it will be log(n), n times.

Hence, O(n log n)

1 Like