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
Anyone can explain 13th?
def f():
ans = 0
for (i = n; i >= 1; i /= 2): // 1
for j = m to i: //2
ans += (i * j)
print(ans)
- loops of this kind runs for log(n) time.
How? You can take example.
n=1 => log2(1) = 0
n=2 => log2(2) = 1
n=4 => log2(4) = 2
… Here n follows pattern.
When n is multiplied by 2 at each step(Which is opposite case than the described case)
In given case i starts from some value n.
In next loop execution i= n/2
… i=n/4
…
…i=n/(2^k) (last execution step of loop)
When i is 1 => n=2^k => k=log(n)
Those are total steps to be computed for each execution.(You can start from k=0 and so on to get value of i for each execution)
You can shortlist options according to which option has log(n). Only one option has log(n) in options so that’s the answer C
- It is not specified if value of m is greater than n or not. So we keep m as it is. And we will take modulus at last as we are using subtraction.
Step 1 : i=n
Executions of statement : (n-m) times
Step 2 : i=n/2
Execution of statement : (n/2 - m) times
Step 3 : i=n/4
Execution of statement : (n/4 - m) times
…
Step k: i=1 (Where n/(n^k) = 1 =>k=log(n) )
Execution of statement : (1 - m) times
To find total executions we take sum of all above step executions
|( n + n/2 + n/4 + … + 1) - m*k |
Replace k by log(n), and taking n common in first bracket
|n(1 + 1/2 + 1/4 + 1/8 …) - m*log(n)|
We can observe that constant term will approach 2 for large value of n.
And x*log(y) has higher priority than z when both terms are present.
So removing first term what we get is : m*log(n) a.k.a. option C
Please Upvote it helped. It was my first answer so sorry if there are any typos or mistakes
Reference : Link to Youtube video and playlist by Mr. Abdul Bari
Thnx, great first answer!!
log(n!)<=nlog(n) i.e. log(n!)=O(nlog(n))
Hi, taran_1407 I think 9th question answer is A. Because inner loop not executed
how to possible j=n and j<i
@admin please help in 17th question what happen if all a element are x then time complexity of programme
Cant figure out the19th question…PLease help!!!
Can someone please explain the solution of Q6,13,14,15,18,20.
Bro it’s pseudo code, if it’s written for j=n to i, it means loop starts from n and decrease value of j till i, more formally it would be same as for(int j=n;j>i;j–)
It’s about finding the first n Fibonacci numbers with memoization( in simple words, DP(Dynamics programming). Google it and read the tutorials to know more about what is dp.
1-c
2-c
3-b
4-b
5-c
6-d
7-c
8-?
9-c
10-b
11-a
12-c
13-c
14-b
15-b
16-?
17-?
18-b
19-?
20-?
21-d
I think
in question no 5 time complexity depend upon the value of “m” and “n” if(m>n) then time complexity is O(m) else O(n).
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
I WAS TOTALLY BLANK AT QUESTION NO 15 CAN ANYONE EXPLAIN THAT PLEASE ???
In Q12, won’t all of the first three options be true because of O(log_2 n) = O(log_{10} n)?
1.B
2.C
3.B
4.B
5.C
6. C
7. C
8. C
9.A
10.B
11.B
12.C
13.B
14.A
15.C
16. B
17. B
18.B
19.B
20. B
21. D
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
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 C
If codes are written in Python, then there is something wrong with Q11. It will run forever because n never will be 0 or negative. I think division should be replaced with floor division in the Q11:
def f(n):
ans = 0
while (n > 0):
ans += n
n //= 2;
print(ans)
Edit: It’s also the case with Q12.