Learn C Coding: GATE Question Based on time complexity

Question 1

What is time complexity of fun()?

int fun(int n)

{

  int count = 0;

  for (int i = n; i > 0; i /= 2)

     for (int j = 0; j < i; j++)

        count += 1;

  return count;

}

A	O(n^2)
B	O(nLogn)
C	O(n)
D	O(nLognLogn)

Discuss it

Question 2

What is the time complexity of fun()?

int fun(int n)

{

  int count = 0;

  for (int i = 0; i < n; i++)

     for (int j = i; j > 0; j--)

        count = count + 1;

  return count;

}

A	Theta (n)
B	Theta (n^2)
C	Theta (n*Logn)
D	Theta (nLognLogn)

Discuss it

Question 3

The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is. (GATE CS 2012)

A	T(n) = 2T(n – 2) + 2
B	T(n) = 2T(n – 1) + n
C	T(n) = 2T(n/2) + 1
D	T(n) = 2T(n – 1) + 1

Discuss it

Question 4

Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE? (GATE CS 2012)
(A) $A(n) = \Omega(W(n))$
(B) $A(n) = \Theta(W(n))$
(C) $A(n) = O(W(n))$
(D) $A(n) = o(W(n))$

A	A
B	B
C	C
D	D

Discuss it

Question 5

Which of the following is not O(n^2)?

A	(15^10) * n + 12099
B	n^1.98
C	n^3 / (sqrt(n))
D	(2^20) * n

Discuss it

Question 6

Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?

  f1(n) = 2^n
  f2(n) = n^(3/2)
  f3(n) = nLogn
  f4(n) = n^(Logn)

A	f3, f2, f4, f1
B	f3, f2, f1, f4
C	f2, f3, f1, f4
D	f2, f3, f4, f1

Discuss it

Question 7

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = D1D2…Dm

int n, rev; 

rev = 0; 

while (n > 0) 

{ 

   rev = rev*10 + n%10; 

   n = n/10; 

}

The loop invariant condition at the end of the ith iteration is: (GATE CS 2004)

A	n = D1D2….Dm-i and rev = DmDm-1…Dm-i+1
B	n = Dm-i+1…Dm-1Dm and rev = Dm-1….D2D1
C	n != rev
D	n = D1D2….Dm and rev = DmDm-1…D2D1

Discuss it

Question 8

What is the time complexity of the below function?

void fun(int n, int arr[])

{

    int i = 0, j = 0;

    for(; i < n; ++i)

        while(j < n && arr[i] < arr[j])

            j++;

}

A	O(n)
B	O(n^2)
C	O(nlogn)
D	O(n(logn)^2)

Discuss it

Question 9

In a competition, four different functions are observed. All the functions use a single for loop and within the for loop, same set of statements are executed. Consider the following for loops:

A) for(i = 0; i < n; i++)

B) for(i = 0; i < n; i += 2)

C) for(i = 1; i < n; i *= 2)

D) for(i = n; i > -1; i /= 2)

If n is the size of input(positive), which function is most efficient(if the task to be performed is not an issue)?

A	A
B	B
C	C
D	D

Discuss it

Question 10

The following statement is valid. log(n!) = $\theta$ (n log n).

A	True
B	False

Discuss it

Question 11

What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

A	X will be a better choice for all inputs
B	X will be a better choice for all inputs except small inputs
C	X will be a better choice for all inputs except large inputs
D	Y will be a better choice for small inputs

Discuss it

Question 12

What is the time complexity of Floyd–Warshall algorithm to calculate all pair shortest path in a graph with n vertices?

A	O(n^2logn)
B	Theta(n^2logn)
C	Theta(n^4)
D	Theta(n^3)

Discuss it

Question 13

Consider the following functions:

  f(n)   = 2^n
  g(n)   = n!
  h(n)   = n^logn

Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?
(A) f(n) = O(g(n)); g(n) = O(h(n))
(B) f(n) = $\Omega$ (g(n)); g(n) = O(h(n))
(C) g(n) = O(f(n)); h(n) = O(f(n))
(D) h(n) = O(f(n)); g(n) = $\Omega$ (f(n))

A	A
B	B
C	C
D	D

Discuss it

Question 14

In the following C function, let n >= m.

int gcd(n,m)

{

  if (n%m ==0) return m;  

  n = n%m;

  return gcd(m, n);

}

How many recursive calls are made by this function?
(A) $\theta$ (logn)
(B) $\Omega$ (n)
(C) $\theta$ (loglogn)
(D) $\theta$ (sqrt(n))

A	A
B	B
C	C
D	D

Discuss it

Question 15

Consider the following functions formula

Which of the following is true? (GATE CS 2000)
(a) h(n) is 0(f(n))
(b) h(n) is 0(g(n))
(c) g(n) is not 0(f(n))
(d) f(n) is 0(g(n))

A	a
B	b
C	c
D	d

Discuss it

Question 16

Consider the following three claims I (n + k)^m = $\theta$ (n^m), where k and m are constants II 2^(n + 1) = 0(2^n) III 2^(2n + 1) = 0(2^n) Which of these claims are correct? (GATE CS 2003)

A	I and II
B	I and III
C	II and III
D	I, II and III

Discuss it

Question 17

Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. which of the following statements is true? (GATE CS 2000)
a) t (n) is 0 (1)
b) n < t (n) < n ${log_2 n}$
c) n log 2 n < t (n) < ${n \choose 2}$
d) t (n) = ${n \choose 2}$

A	a
B	b
C	c
D	d

Discuss it

Question 18

Consider the following function

 int unknown(int n) {
    int i, j, k = 0;
    for (i  = n/2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n/2;
    return k;
 }

What is the returned value of the above function? (GATE CS 2013)

(A) 
(B) 
(C) 
(D)

A	A
B	B
C	C
D	D

Discuss it

Question 19

Consider the following two functions. What are time complexities of the functions?

int fun1(int n)

{

    if (n <= 1) return n;

    return 2*fun1(n-1);

}

int fun2(int n)

{

    if (n <= 1) return n;

    return fun2(n-1) + fun2(n-1);

}

A	O(2^n) for both fun1() and fun2()
B	O(n) for fun1() and O(2^n) for fun2()
C	O(2^n) for fun1() and O(n) for fun2()
D	O(n) for both fun1() and fun2()

Discuss it

Question 20

Consider the following segment of C-code:

  int j, n;
  j = 1;
  while (j <= n)
        j = j*2;

The number of comparisons made in the execution of the loop for any n > 0 is: Base of Log is 2 in all options.

A	CEIL(logn) + 1
B	n
C	CEIL(logn)
D	FLOOR(logn) + 1

Discuss it

Question 21

Consider the following C-program fragment in which i, j and n are integer variables.

for (i = n, j = 0; i >0; i /= 2, j += i);

Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true? (A) val(j) = $\theta$ (logn) (B) vaI(j) = $\theta$ (sqrt(n)) (C) val(j) = $\theta$ (n) (D) val(j) = $\theta$ (nlogn)

A	A
B	B
C	C
D	D

Discuss it

Question 22

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.

A	147.1 to 148.1
B	145.1 to 146.1
C	140 to 146
D	140 to 148

Discuss it

Question 23

Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2
for i = 1 to n do
   for j = i to n do
      for k = j + 1 to n do
           D = D * 3

A	Half of the product of the 3 consecutive integers.
B	One-third of the product of the 3 consecutive integers.
C	One-sixth of the product of the 3 consecutive integers.
D	None of the above.

Discuss it

Question 24

Consider the following C-function:

double foo (int n)

{

    int i;

    double sum;

    if (n = = 0) return 1.0;

    else

    {

        sum = 0.0;

        for (i = 0; i < n; i++)

            sum += foo (i);

        return sum;

    }

}

The space complexity of the above function is:

A	O(1)
B	O(n)
C	O(n!)
D	O(nⁿ)

Discuss it

Question 25

Consider the following C-function:

double foo (int n)

{

    int i;

    double sum;

    if (n = = 0) return 1.0;

    else

    {

        sum = 0.0;

        for (i = 0; i < n; i++)

            sum += foo (i);

        return sum;

    }

}

Suppose we modify the above function foo() and store the values of foo (i), 0 < = i < n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be:

A	O(1)
B	O(n)
C	O(n!)
D	O(nⁿ)

Discuss it

Question 26

Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M1 × M2 will be

A	best if A is in row-major, and B is in column- major order
B	best if both are in row-major order
C	best if both are in column-major order
D	independent of the storage scheme

Discuss it

Question 27

Let A[1, ..., n] be an array storing a bit (1 or 0) at each location, and f(m) is a unction whose time complexity is θ(m). Consider the following program fragment written in a C like language:

counter = 0;

for (i = 1; i < = n; i++)

{ 

      if (A[i] == 1) 

         counter++;

      else {

         f(counter); 

         counter = 0;

      }

}

The complexity of this program fragment is

A	Ω(n²)
B	Ω(nlog n) and O(n²)
C	θ(n)
D	O(n)

Question 28

The recurrence equation

T(1) = 1
T(n) = 2T(n - 1) + n, n ≥ 2

evaluates to

A	2^{n + 1}- n - 2
B	2ⁿ - n
C	2^{n + 1} - 2n - 2
D	2ⁿ - n

Question 29

Consider the following three claims

1. (n + k)^m = Θ(n^m), where k and m are constants
2. 2^{n + 1} = O(2ⁿ)
3. 2^{2n + 1} = O(2ⁿ)

Which of these claims are correct ?

A	1 and 2
B	1 and 3
C	2 and 3
D	1, 2, and 3

Question 30

The increasing order of following functions in terms of asymptotic complexity is:

A	f1(n); f4(n); f2(n); f3(n)
B	f1(n); f2(n); f3(n); f4(n);
C	f2(n); f1(n); f4(n); f3(n)
D	f1(n); f2(n); f4(n); f3(n)

Answer and Explanation

1. C

Question 1 Explanation:

For a input integer n, the innermost statement of fun() is executed following times. So time complexity T(n) can be written as T(n) = O(n + n/2 + n/4 + ... 1) = O(n) The value of count is also n + n/2 + n/4 + .. + 1

2. B

Question 2 Explanation:

The time complexity can be calculated by counting number of times the expression "count = count + 1;" is executed. The expression is executed 0 + 1 + 2 + 3 + 4 + .... + (n-1) times. Time complexity = Theta(0 + 1 + 2 + 3 + .. + n-1) = Theta (n*(n-1)/2) = Theta(n^2)

3.D

Question 3 Explanation:

Following are the steps to follow to solve Tower of Hanoi problem recursively.

Let the three pegs be A, B and C. The goal is to move n pegs from A to C.
To move n discs from peg A to peg C:
    move n-1 discs from A to B. This leaves disc n alone on peg A
    move disc n from A to C
    move n?1 discs from B to C so they sit on disc n

The recurrence function T(n) for time complexity of the above recursive solution can be written as following. T(n) = 2T(n-1) + 1

4..C

Question 4 Explanation:

The worst case time complexity is always greater than or same as the average case time complexity.

5.C

Question 5 Explanation:

The order of growth of option c is n^2.5 which is higher than n^2.

6.A

7.A

Learn C Coding

Saturday 31 January 2015

GATE Question Based on time complexity

3 comments: