Please explain me 21st question’s solution.
I think Q.17th should have answer c) because we are considering worst case complexity here
4 Likes
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-C
20-D
21-C
Please someone explain Q.no 4?
according to me its log (n!)
4 Likes
can anyone explain problem 6 and 18
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
1 B
2 C
3 B
4 B
5 C
6 D
7 C
8 D
9 C
Three Loops are there so for single loop complexity will be “n” for three loop complexity will be “n^3”
10 B
11 A
12 C
13 C
14 B
15 C
16 B
17 B
18 D
19 B
20 B
21 C
As both n and m are the input parameters of the function. So, we should give \mathcal{O}(n + m) as time complexity.
1 Like
kudos, I think all your answers are correct 
Really?
I guessed 2nd and 15th. 
yes, they are right too.
Since counter increases by 1, of course, it is expected to be O(N) worst case.
1 Like
So if number of occurrences of x are m then complexity will be O(m).
1 Like
Yes. The main focus was, it takes O(LogN) time to find ocurrances of x in the sorted array. I think this question goes by an assumption that “Number of occurances of x very less than Number of elements in array.”
3 Likes
Yes, You are absolutely right @akash_321, Though there exist a better way to count number of occurance of an element in a sorted array in O(logN) time.
1 Like
Just remember to set correct upper limit 
j does not get re-initialized every step. Its initialized to 0 only once, and remembers the value of previous iteration. So, once it reaches n, inner loop will never execute. Hence the algo will execute maximum 2n times.
Since when we started assuming things, that too on codechef.
big O is always worst case complexity.