MCQs about Time and Space Complexity Of a Program

tutorial
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

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?