You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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)$
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[i][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[i][j]
print(sum)

for i = 1 to n:
sum -= a[i][i]


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[i][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;


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[i] < 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)$

This question is marked "community wiki".

asked 30 Jan '18, 19:29 19.8k350498541
accept rate: 36% 15.5k12066

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

(11 Jun '18, 09:43) 2★

 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 answered 30 Jan '18, 21:51 4.0k●31●103 accept rate: 22% kudos, I think all your answers are correct :) (30 Jan '18, 22:35) admin ♦♦0★ Really? I guessed 2nd and 15th. :D (31 Jan '18, 00:54) yes, they are right too. (31 Jan '18, 02:23) admin ♦♦0★
 3 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 76●5 accept rate: 0% 1 @akash_321: Yes, you are right. It will be $\mathcal{O}(n)$. (06 Feb '18, 14:02) admin ♦♦0★ 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) 1 Yes, surely i will. :D @vijju123 (07 Feb '18, 00:02) 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
 0 Wouldn't question 5 depend on the bigger number(n or m)? In that case it could be either a or b, right? answered 30 Jan '18, 21:24 1 accept rate: 0% 1 As both n and m are the input parameters of the function. So, we should give $\mathcal{O}(n + m)$ as time complexity. (30 Jan '18, 22:34) admin ♦♦0★
 0 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 1 accept rate: 0%
 0 Please explain the soln. for Q.20. answered 16 Mar '18, 19:59 3★mnjn25 27●2 accept rate: 33% 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. (16 Mar '18, 20:14)
 0 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 \times m)$. Question 21: Has no options C, and two options D. The correct choice is the first option D! answered 17 Mar '18, 01:28 605●1●7 accept rate: 26%
 0 Could someone please explain why the answer of question 21 is $\mathcal{O}(n\log n)$? answered 08 May '18, 18:26 162●7 accept rate: 10% Check derivation of "Sieve ofErastothenes" . Its similar to that. (08 May '18, 18:54) it is n(1+1/2+1/3+1/4+...1/n). The sum in brackets converges to log(n) as n->inf. It is just a known mathematical result. (21 Jun '18, 19:52)
 0 q12 Theoretically , A,B,C are all correct answered 12 May '18, 23:40 111●1●6 accept rate: 11% Theoretically, yes. But the intent of the problem setter to check whether you understand the base of the logarithmic or not ;) (01 Jun '18, 14:51) admin ♦♦0★
 0 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) answered 01 Jun '18, 10:21 1 accept rate: 0% The explanation is correct :) But you can explain a bit about harmonic sum and then say that the harmonic sum is bounded by $\log{n}$, hence, we get an $\mathcal{O}(n \log{n})$ time algorithm. (01 Jun '18, 14:52) admin ♦♦0★
 0 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 1 accept rate: 0%
 0 Please explain question number 15 although i guessed it correct?? answered 20 Jun '18, 23:16 1 accept rate: 0%
 0 Q 15 anyone? Where can i see list of all different big oh complexity? answered 21 Jun '18, 08:11 0★nagpalji 1 accept rate: 0%
 0 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 1 accept rate: 0%
 0 Please explain me 21st question's solution. answered 10 Jul '18, 17:49 0★im_sumit 1 accept rate: 0%
 0 I think Q.17th should have answer c) because we are considering worst case complexity here answered 21 Jul '18, 16:41 1★him27_di 1 accept rate: 0%
 0 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 link This answer is marked "community wiki". answered 18 Aug '18, 13:13 1●1 accept rate: 0%
 0 Please someone explain Q.no 4? according to me its log (n!) answered 07 Oct '18, 21:14 2★indsonu 1 accept rate: 0%
 0 can anyone explain problem 6 and 18 answered 27 Dec '18, 20:46 0★sawan_97 1 accept rate: 0%
 0 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 accept rate: 0%
 0 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 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×712

question asked: 30 Jan '18, 19:29

question was seen: 13,167 times

last updated: 24 Feb, 00:03