MCQs about Time and Space Complexity Of a Program

tutorial
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
104

Anyone can explain 20 and 21 plzz

105

For 20, j loop will run totally from j=0 to j=n over all i. So, j loop is running only one time. Time comp is O(n)
For 21,
for i=1, second loop will have n/1 iteration
for i=2, iteration=n/2
…
for i=n, iteration=n/n
total=n/1 + n/2 + n/3 + … + n/n
=n(1/1 + 1/2 + 1/3 + … + 1/n)
=nlogn
So, time comp is O(nlgn)

1 Like
106

B
C
B
B
C
C
C
C
C
B
A
C
C
B
B
B
B
C
B
D
D

107

I got all correct as per your response except below ones:
18. C -> D
20. D -> B
21. D -> C

108
109

Thanks, I now saw these replies from previous posts as well.

110
  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
111

The catch point here is that 1 + 1/2 + 1/3 … 1/n is the expansion of log(n) series, hence the answer is nlog(n)

112

@praveenkumar12
can you please tell whats is the sum of expansion if the sequence is
n(1+1/2+1/4+1/8+1/16+…1/n)
what would be the time complexity for this one.

113

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

114
  • List item
    question option
    Q1 B
    Q2 C
    Q3 D
    Q4 B
    Q5 C
    Q6 C
    Q7 C
    Q8 C
    Q9 C
    Q10 B
    Q11 A
    Q12 D
    Q13 C
    Q14 B
    Q15 C
    Q16 B
    Q17 B
    Q18 D
    Q19 B
    Q20 B
    Q21 C
115

you are Wright, In worst case it’s O(n) in question no. 17