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]
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
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
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)
Anyone can explain 20 and 21 plzz
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)
B
C
B
B
C
C
C
C
C
B
A
C
C
B
B
B
B
C
B
D
D
I got all correct as per your response except below ones:
18. C -> D
20. D -> B
21. D -> C
Thanks, I now saw these replies from previous posts as well.
- b
- c
- b
- b
- c
- d
- c
- c
- c
- b
- a
- c
- c
- b
- b
- b
- b
- d
- b
- b
- c
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)
@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.
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
- 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
you are Wright, In worst case it’s O(n) in question no. 17
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)
Spoiler
O(2^n).
It’s like incrementing a binary number.
O(\log^2{MAXA})
yes
no, although closer than most complexities I have seen in the replies there.
17th question shouldn’t it be O(n)??