MCQs about Time and Space Complexity Of a Program

tutorial
123

Who said you that log base 2 of n= log base 10 of n

124

1- B
2- C
3 B
4- B
5- C
6- C
7 -C
8- C
9 -C
10 -B
11- A
12- C
13 -C
14 -A
15
16 -B
17 -B
18- D
19
20 - B
21-D

125

I think 17 should be O(n)? Worst case if all the elements are equal to x.

For \log(n) we should write upperbound and lowerbound kind of binary search.

1 Like
126

He is right. \log_2n \ne log_{10}n, but you can certainly say \mathcal O(\log_2n) = \mathcal O(\log_{10}n). Just like how you would say, \mathcal O(2n) = \mathcal O(n). So theoretically speaking, A, B, C all are right for Q12.

If the options were \theta(\log_bn) instead, then only b = 10 will be right.

You are right. If there was such an option, we would choose it. But as there isn’t one, consider this:

\log 1 + \log 2 + \log 3 + \cdots + \log n \le \log n + \log n + \log n + \cdots +\log n

Hence,

\mathcal O( \log 1 + \log 2 + \log 3 + \cdots + \log n) = \mathcal O ( \log n + \log n + \log n + \cdots +\log n)
\mathcal O(\log(n!)) = \mathcal O(n\log n)

Or,

\mathcal O(\log(n!)) = \mathcal O(log n^n) = \mathcal O(n \log n)

As the option \mathcal O(n \log n) is available, we choose it. Doesn’t mean you are wrong, \mathcal O(\log (n!)) is also right.

2 Likes
127

Answers-
Q1 - B
Q2 - C
Q3 - B
Q4- B
Q5- C
Q6- D
Q7- C
Q8- C
Q9- C
Q10-B
Q11 -A
Q12-C
Q13-C
Q14-B
Q15-B
Q16-B
Q17-C
Q18-D
Q19-B
Q20-B
Q21-C

128

Well Explaned and correct

1 Like
129

it is n +n/2+2/3+n/3+n/4
+n/n = n(1/1+1/2+1/3+
+1/n) = nlogn
in bracket, there is a harmonic series which converges to logn.
so, nlogn should be the ans.

130

How did you arrive at option B for ques 17? I got C. Could you please explain?

131
  • 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
132

O(n)

133

Answer to the 6th qs would be O((nm) + n) which ofc is O(n*m)
right? That plus n factor because even the outer loop contains statements that would be executed
right?

134

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 C (No idea, guessed)
16 B
17 B
18 D
19 B
20 B
21 C

135

It is known as Optimized Ecliudean Algorithm, it is a recursive function which finds the mod of the second term( greater term) by smaller term which results in O(log n) time, that is the reason it swaps the terms if a<b in the first condition, so the we don’t have to subtract repeatedly to find the gcd.

136

1 (B)
2 ©
3 (A)
4 (B)
5 ©
6 (D)
7 ©
8 ©
9 ©
10 (B)
11 (A)
12 ©
13 ©
14 (B)
15 (B)
16 (B)
17 (B)
18 (D)
19 (B) not sure about this
20 (D)
21 ©

137
  1. O(nlogn)
  2. O(n**2)
  3. O(logn)
  4. O(n**2)
  5. O(n+m)
  6. O(n*m)
  7. O(n**2)
  8. O(n**2)]
  9. O(n**2)
  10. O(nmk)
  11. O (log n)
  12. O(log 10 n)
  13. O(m log n)
  14. O(log m log n)
  15. O(log n)
  16. O(log n)
  17. O(log n)
  18. O(2**n)
  19. O(log n)
    20.O(n**2)
  20. O(nlogn)
138

O(n logn)

139

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 a

140

can you explain q-6 and q-19?

141

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(guess)
14-B
15-A(guess)
16-B
17-B(guess)
18-D
19-(no idea)
20-D
21-C

142

def f():
ans = 0
for i = 1 to n:
for j = i; j <= n; j += i:
ans += 1
print(ans)
u jst see the first for loop which is giving O(n) now see the second one it is like log(n) because we are adding value of i to j after every iteration of j ,
now, we know if there is a loop within a loop we simply multiply , that is why answer is O(n logn).