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

10
9

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

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

edited 27 Apr '18, 16:08

vijju123's gravatar image

5★vijju123 ♦♦
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) flaze072★

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

link

answered 30 Jan '18, 21:51

taran_1407's gravatar image

6★taran_1407
4.0k31103
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) taran_14076★

yes, they are right too.

(31 Jan '18, 02:23) admin ♦♦0★

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

link

answered 05 Feb '18, 16:11

akash_321's gravatar image

4★akash_321
765
accept rate: 0%

edited 06 Feb '18, 13:40

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) vijju123 ♦♦5★

So if number of occurrences of x are m then complexity will be O(m).

(06 Feb '18, 15:04) akash_3214★
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) vijju123 ♦♦5★
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) taran_14076★

Just remember to set correct upper limit :p

(06 Feb '18, 23:41) vijju123 ♦♦5★
1

Yes, surely i will. :D @vijju123

(07 Feb '18, 00:02) taran_14076★

Since when we started assuming things, that too on codechef. :) big O is always worst case complexity.

(27 Apr '18, 00:05) rahul_mishra012★
showing 5 of 8 show all

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

link

answered 30 Jan '18, 21:24

benritmico's gravatar image

4★benritmico
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★

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

link

answered 03 Mar '18, 22:04

kunalk0214's gravatar image

1★kunalk0214
1
accept rate: 0%

Please explain the soln. for Q.20.

link

answered 16 Mar '18, 19:59

mnjn25's gravatar image

3★mnjn25
272
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) vijju123 ♦♦5★

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!

link

answered 17 Mar '18, 01:28

john_smith_3's gravatar image

6★john_smith_3
60517
accept rate: 26%

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

link

answered 08 May '18, 18:26

the_extractor's gravatar image

4★the_extractor
1627
accept rate: 10%

Check derivation of "Sieve ofErastothenes" . Its similar to that.

(08 May '18, 18:54) vijju123 ♦♦5★

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) praveenkumar125★

q12 Theoretically , A,B,C are all correct

link

answered 12 May '18, 23:40

gagan86nagpal's gravatar image

5★gagan86nagpal
11116
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★

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)

link

answered 01 Jun '18, 10:21

the_mainak's gravatar image

3★the_mainak
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★

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

link

answered 08 Jun '18, 20:38

saiganeshraja's gravatar image

0★saiganeshraja
1
accept rate: 0%

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

link

answered 20 Jun '18, 23:16

mriganksingh's gravatar image

2★mriganksingh
1
accept rate: 0%

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

link

answered 21 Jun '18, 08:11

nagpalji's gravatar image

0★nagpalji
1
accept rate: 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.

link

answered 02 Jul '18, 16:47

thedheeraj008's gravatar image

2★thedheeraj008
1
accept rate: 0%

Please explain me 21st question's solution.

link

answered 10 Jul '18, 17:49

im_sumit's gravatar image

0★im_sumit
1
accept rate: 0%

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

link

answered 21 Jul '18, 16:41

him27_di's gravatar image

1★him27_di
1
accept rate: 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

nimishgupta95's gravatar image

0★nimishgupta95
11
accept rate: 0%

edited 18 Aug '18, 13:20

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

link

answered 07 Oct '18, 21:14

indsonu's gravatar image

2★indsonu
1
accept rate: 0%

can anyone explain problem 6 and 18

link

answered 27 Dec '18, 20:46

sawan_97's gravatar image

0★sawan_97
1
accept rate: 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

link

answered 17 Feb, 03:07

shahramatrian's gravatar image

0★shahramatrian
1
accept rate: 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

link

answered 24 Feb, 00:03

abhishek10548's gravatar image

0★abhishek10548
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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