Multiple Choice Questions Related To Testing Knowledge about Time and Space Complexity Of A Program

tutorial

#1

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 :slight_smile:

Q1.

Average case time complexity of quicksort?

A. \mathcal{O}(n)
B. \mathcal{O}(n \log n)
C. \mathcal{O}(n^2)
D. \mathcal{O}(n^3)


Q2.

Worst case time complexity of quicksort?

A. \mathcal{O}(n)
B. \mathcal{O}(n \log n)
C. \mathcal{O}(n^2)
D. \mathcal{O}(n^3)


Q3.

Time complexity of binary search?

A. \mathcal{O}(1)
B. \mathcal{O}(\log n)
C. \mathcal{O}({(\log n)}^2)
D. \mathcal{O}(n)


Q4.

def f()
	ans = 0
	for i = 1 to n:
		for j = 1 to log(i):
			ans += 1
	print(ans)

Time Complexity of this program:

A. \mathcal{O}(n)
B. \mathcal{O}(n \log n)
C. \mathcal{O}(n^2)
D. \mathcal{O}(n^3)


Q5.

def f():
	a = 0
	for i = 1 to n:
		a += i;
	b = 0
	for i = 1 to m:
		b += i;

Time Complexity of this program:

A. \mathcal{O}(n)
B. \mathcal{O}(m)
C. \mathcal{O}(n + m)
D. \mathcal{O}(n * m)


Q6.

def f():
	a = 0
	for i = 1 to n:
		a += random.randint();			
		b = 0
		for j = 1 to m:
			b += random.randint();

Time Complexity of this program:

A. \mathcal{O}(n)
B. \mathcal{O}(m)
C. \mathcal{O}(n + m)
D. \mathcal{O}(n * m)


Q7.

def f():
	int a[n][n]
	// Finding sum of elements of a matrix that are above or on the diagonal.
	sum = 0
	for i = 1 to n:
		for j = i to n:
			sum += a*[j]
	print(sum)

Time Complexity of this program:

A. \mathcal{O}(n)
B. \mathcal{O}(n \log n)
C. \mathcal{O}(n^2)
D. \mathcal{O}(n^3)


Q8.

def f():
	int a[n][n]
	sum = 0
	// Finding sum of elements of a matrix that are strictly above the diagonal.
	for i = 1 to n:
		for j = i to n:
			sum += a*[j]
	print(sum)
	
	for i = 1 to n:
		sum -= a**

Time Complexity of this program:

A. \mathcal{O}(n)
B. \mathcal{O}(n \log n)
C. \mathcal{O}(n^2)
D. \mathcal{O}(n^3)


Q9.

def f():
	ans = 0
	for i = 1 to n:
		for j = n to i:
			ans += (i * j)
	print(ans)

Time Complexity of this program:

A. \mathcal{O}(n)
B. \mathcal{O}(n \log n)
C. \mathcal{O}(n^2)
D. \mathcal{O}(n^3)


Q10.

def f():
	int a[N + 1][M + 1][K + 1]
	sum = 0
	for i = 1 to N:
		for j = i to M:
			for k = j to K:
				sum += a*[j]
	print(sum)

Time Complexity of this program:

A. \mathcal{O}(N + M + K)
B. \mathcal{O}(N * M * K)
C. \mathcal{O}(N * M + K)
D. \mathcal{O}(N + M * K)


Q11.

def f(n):
	ans = 0
	while (n > 0):
		ans += n
		n /= 2;
	print(ans)

Time Complexity of this program:

A. \mathcal{O}(\log n)
B. \mathcal{O}(n)
B. \mathcal{O}(n \log n)
C. \mathcal{O}(n^2)


Q12.

// Find the sum of digits of a number in its decimal representation.
def f(n):
	ans = 0
	while (n > 0):
		ans += n % 10
		n /= 10;
	print(ans)

Time Complexity of this program:

A. \mathcal{O}(\log_2 n)
B. \mathcal{O}(\log_3 n)
C. \mathcal{O}(\log_{10} n)
D. \mathcal{O}(n)


Q13.

def f():
	ans = 0
	for (i = n; i >= 1; i /= 2):
		for j = m to i:
			ans += (i * j)
	print(ans)

Time Complexity of this program:

A. \mathcal{O}(n + m)
B. \mathcal{O}(n * m)
C. \mathcal{O}(m \log n)
D. \mathcal{O}(n \log m)


Q14.

def f():
	ans = 0
	for (i = n; i >= 1; i /= 2):
		for (j = 1; j <= m; j *= 2)
			ans += (i * j)
	print(ans)

Time Complexity of this program:

A. \mathcal{O}(n * m)
B. \mathcal{O}(\log m \log n)
C. \mathcal{O}(m \log n)
D. \mathcal{O}(n \log m)


Q15.

// Finding gcd of two numbers a, b.
def gcd(a, b):
	if (a < b) swap(a, b)
	if (b == 0) return a;
	else return gcd(b, a % b)

Time Complexity of this program:

Let n = \max\{a, b\}

A. \mathcal{O}(1)
B. \mathcal{O}(\log n)
C. \mathcal{O}(n)
D. \mathcal{O}(n^2


Q16.

// Binary searching in sorted array for finding whether an element exists or not.
def exists(a, x):
	// Check whether the number x exists in the array a.
	lo = 0, hi = len(a) - 1
	while (lo <= hi):
		mid = (lo + hi) / 2
		if (a[mid] == x): return x;
		else if (a[mid] > x): hi = mid - 1;
		else lo = mid + 1;
	return -1; // Not found.

Time Complexity of this program:

Let n = len(a)

A. \mathcal{O}(1)
B. \mathcal{O}(\log n)
C. \mathcal{O}(n)
D. \mathcal{O}(n^2


Q17.

// Given a sorted array a, find the number of occurrence of number x in the entire array.

def count_occurrences(a, x, lo, hi):
	if lo > hi: return 0
	mid = (lo + hi) / 2;
	if a[mid] < x: return count_occurrences(a, x, mid + 1, hi)
	if a[mid] > x: return count_occurrences(a, x, lo, mid - 1)
	return 1 + count_occurrences(a, x, lo, mid - 1) + count_occurrences(a, x, mid + 1, hi)

// in the main function, we call it as
count_occurrences(a, x, 0, len(a) - 1)

Time Complexity of this program:

Let n = len(a)

A. \mathcal{O}(1)
B. \mathcal{O}(\log n)
C. \mathcal{O}(n)
D. \mathcal{O}(n^2


Q18.

// Finding fibonacci numbers.
def f(n):
	if n == 0 or n == 1: return 1
	return f(n - 1) + f(n - 2)

Time Complexity of this program:

A. \mathcal{O}(\log n)
B. \mathcal{O}(n)
C. \mathcal{O}(n^2)
D. \mathcal{O}(2^n)


Q19.

Create array memo[n + 1]

// Finding fibonacci numbers with memoization.
def f(n):
	if memo[n] != -1: return memo[n]
	if n == 0 or n == 1: ans = 1
	else: ans = f(n - 1) + f(n - 2)
	memo[n] = ans
	return ans

// In the main function.
Fill the memo array with all values equal to -1.
ans = f(n)

Time Complexity of this program:

A. \mathcal{O}(\log n)
B. \mathcal{O}(n)
C. \mathcal{O}(n^2)
D. \mathcal{O}(2^n)


Q20.

def f(a):
	n = len(a)
	j = 0
	for i = 0 to n - 1:
		while (j < n and a* < a[j]):
			j += 1

Time Complexity of this program:

A. \mathcal{O}(\log n)
B. \mathcal{O}(n)
C. \mathcal{O}(n \log n)
D. \mathcal{O}(n^2)


Q21.

def f():
	ans = 0
	for i = 1 to n:
		for j = i; j <= n; j += i:
			ans += 1
	print(ans)

Time Complexity of this program:

A. \mathcal{O}(\log n)
B. \mathcal{O}(n)
C. \mathcal{O}(n \log n)
D. \mathcal{O}(n^2)


#2

Wouldn’t question 5 depend on the bigger number(n or m)? In that case it could be either a or b, right?


#3

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 (No idea, though i guess this)
16 B
17 B
18 D
19 B
20 B
21 C


#4

In question 17 if all elements of a are x wouldn’t the complexity be O(n).
@taran_1407 @admin @vijju123 anyone?


#5

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


#6

Please explain the soln. for Q.20.


#7

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).

The only choice available that is big enough is B: {\scr O}(n imes m).

Question 21:

Has no options C, and two options D. The correct choice is the first option D!


#8

Could someone please explain why the answer of question 21 is \mathcal{O}(n\log n)?


#9

q12 Theoretically , A,B,C are all correct


#10

Question 21 explained:

Here outer for loop (loop i) will run n times.
when i=1, inner loop (loop j) will run n/1 times [for j = 1; j <= n; j += 1]
when i=2, inner loop will run n/2 times [for j = 2; j <= n; j += 2]
…upto i=n, inner loop will run n/n=1 time [for j = n; j <= n; j += n]
So, Total time= O(n+ n/2+ n/3+ …+ n/n)
=O(n(1+1/2 +1/3+…+1/n))
=O(nlogn)


#11

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


#12

Please explain question number 15 although i guessed it correct??


#13

Q 15 anyone? Where can i see list of all different big oh complexity?


#14

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.


#15

Please explain me 21st question’s solution.


#16

I think Q.17th should have answer c) because we are considering worst case complexity here


#17

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


#18

Please someone explain Q.no 4?
according to me its log (n!)


#19

can anyone explain problem 6 and 18


#20

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