Hi fellow programmers, We are trying to create a multiple choice quiz for space and time complexity of the programs related questions. Here are a set of 20 questions we collected. Please feel free to give your answers to these questions. Any feedback about the set of questions. Please also feel propose to any more set of MCQs that you would like to add here, there might be some interesting questions that you might have encountered during the programming and would like to add here :) Q1.Average case time complexity of quicksort? A. $\mathcal{O}(n)$ Q2.Worst case time complexity of quicksort? A. $\mathcal{O}(n)$ Q3.Time complexity of binary search? A. $\mathcal{O}(1)$ Q4.
Time Complexity of this program: A. $\mathcal{O}(n)$ Q5.
Time Complexity of this program: A. $\mathcal{O}(n)$ Q6.
Time Complexity of this program: A. $\mathcal{O}(n)$ Q7.
Time Complexity of this program: A. $\mathcal{O}(n)$ Q8.
Time Complexity of this program: A. $\mathcal{O}(n)$ Q9.
Time Complexity of this program: A. $\mathcal{O}(n)$ Q10.
Time Complexity of this program: A. $\mathcal{O}(N + M + K)$ Q11.
Time Complexity of this program: A. $\mathcal{O}(\log n)$ Q12.
Time Complexity of this program: A. $\mathcal{O}(\log_2 n)$ Q13.
Time Complexity of this program: A. $\mathcal{O}(n + m)$ Q14.
Time Complexity of this program: A. $\mathcal{O}(n * m)$ Q15.
Time Complexity of this program: Let $n = \max\{a, b\}$ A. $\mathcal{O}(1)$ Q16.
Time Complexity of this program: Let $n = len(a)$ A. $\mathcal{O}(1)$ Q17.// Given a sorted array a, find the number of occurrence of number x in the entire array.
Time Complexity of this program: Let $n = len(a)$ A. $\mathcal{O}(1)$ Q18.
Time Complexity of this program: A. $\mathcal{O}(\log n)$ Q19.
Time Complexity of this program: A. $\mathcal{O}(\log n)$ Q20.
Time Complexity of this program: A. $\mathcal{O}(\log n)$ Q21.
Time Complexity of this program: A. $\mathcal{O}(\log n)$
This question is marked "community wiki".
asked 30 Jan '18, 19:29

In question 17 if all elements of a are x wouldn't the complexity be O(n). @taran_1407 @admin @vijju123 anyone? answered 05 Feb '18, 16:11
1
Since counter increases by 1, of course, it is expected to be $O(N)$ worst case.
(06 Feb '18, 14:55)
So if number of occurrences of x are m then complexity will be O(m).
(06 Feb '18, 15:04)
2
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."
(06 Feb '18, 15:17)
1
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.
(06 Feb '18, 23:26)
Just remember to set correct upper limit :p
(06 Feb '18, 23:41)
Since when we started assuming things, that too on codechef. :) big O is always worst case complexity.
(27 Apr '18, 00:05)
showing 5 of 8
show all

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 a answered 03 Mar '18, 22:04

Question 13: If $n$ is large, and $m$ is small, then the innermost statement is executed $n + n/2 + n/4 + \ldots $ times. So the problem is at least ${\scr O}(n)$. If $n$ and $m$ are large, then the innermost statement is executed roughly $m \log n$ times. So I believe the problem as a whole is ${\scr O}(n+m\log n)$. Question 21: Has no options C, and two options D. The correct choice is the first option D! answered 17 Mar '18, 01:28

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.C 19.B 20.B 21.A answered 08 Jun '18, 20:38

Please explain question number 15 although i guessed it correct?? answered 20 Jun '18, 23:16

Q 15 anyone? Where can i see list of all different big oh complexity? answered 21 Jun '18, 08:11

Q17. Considering the worst case scenario if the whole array contains a duplicate entry, the algorithm has to go O(n) times to calculate the occurrence. According to me, it should be C. Correct me if I'm wrong. answered 02 Jul '18, 16:47

I think Q.17th should have answer c) because we are considering worst case complexity here answered 21 Jul '18, 16:41

1B 2C 3B 4B 5C 6D 7C 8C 9C 10B 11A 12C 13C 14B 15B 16B 17B 18D 19C 20D 21C
link
This answer is marked "community wiki".
answered 18 Aug '18, 13:13

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 answered 17 Feb, 03:07

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 answered 24 Feb, 00:03

I am curious as to how to know the complexity of a program, I have binged ( I don't use google ) the answer, and I found it in several places( SO, wikipedia included ) and I never understand any of the explanation