MCQs about Time and Space Complexity Of a Program

tutorial
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

116

1 B,C,D
2 C,D
3 B,C,D
4 B,C,D
5 C, D
6 D
7 C,D
8 C,D
9 C,D; assuming j=n to i to mean to iterate j over n, n-1, n-2, … i
10 A,B,C,D ; runtime error because can’t add array to int
11 A,B,C,D
12 A,B,C,D
13 B,C; if m were to be 0 it will be \Theta(n)
14 A,B,C,D
15 B,C,D
16 B,C,D
17 C,D ; though this could be done in \Theta(\log n) using two binary searches.
18 D
19 B,C,D
20 B,C,D
21 C,D

2 tricky questions:

int main() {
    int n;
    cin >> n;
    vector<bool> a(n,false)
    for (int i = 0;i<n;i++) {
        a[i] = not a[i];
        if (a[i]==1) {
            i = 0;
        }
    }
    return 0;
}

And of course
The runtime complexity of ORTHODOX

And different to the OP’s question I want the tightest complexity (which is called \Theta)

1 Like
117
Spoiler

O(2^n).
It’s like incrementing a binary number.
O(\log^2{MAXA})

118

yes
no, although closer than most complexities I have seen in the replies there.

119

17th question shouldn’t it be O(n)??

120

i also think that the time complexity of 17 can be O(n)

121

@taran_1407 @aneee004 @everule1 the for the 4th question
The loop for I=1 is going log(1) times , the the loop for i=2 is going log(2) times , the loop for I=3 is going log(3) times , and so on , so shouldn’t the total time be log(1)+log(2) + log(3)+…+log(n) = log(n!) , Though that is not in the options , please correct me if I am wrong

122

n>0 is written and not n>=0 , n=0 is also a case where it can fail