DAA 2023- 2024 Test 2

What is the time complexity of this code

int a = 0, i = N;

while (i > 0)

{

a += i;

i /= 2;

}

• O(N)

• O(Sqrt(N))

• O(N / 2)

• O(log N)

Time Complexity of this program:

def f():

a = 0

for i = 1 to n:

a += i;

b = 0

for i = 1 to m:

b += i;

• O(n)

• O(m)

• O(n+m)

• O(n*m)

What is the time complexity of following code:

int a = 0;

for (i = 0; i < N; i++) {

for (j = N; j > i; j--) {

a = a + i + j;

}

}

• O(N)

• O(N*log(N))

• O(N * Sqrt(N))

• O(N*N)

What is the time complexity of following code:

int i, j, k = 0;

for (i = n / 2; i <= n; i++) {

for (j = 2; j <= n; j = j * 2) {

k = k + n / 2;

}

}

• O(n)

• O(nLogn)

• O(n^2)

• O(n^2Logn)

Which of the problems cannot be solved by backtracking method?

• n-queen problem

• subset sum problem

• Hamiltonian circuit problem

• travelling salesman problem

Backtracking algorithm is implemented by constructing a tree of choices called as?

• State-space tree

  
  

• state chart tree

• node tree

• Backtracking tree

Which of the following problems is similar to that of a Hamiltonian path problem?

• Knapsack problem

• closest pair problem

• travelling salesman problem

• assignment problem

Branch and bound is a __________

• problem solving technique

• data structure

• sorting algorithm

• type of tree

Choose the correct statement from the following.

• Greedy method is efficient than dynamic programming approach

• Backtracking approach gives only one optimal solution

• Branch and bound can be used for solving Optimization problems

• None of these

Which of the following problems is NOT solved using dynamic programming?

• 0/1 knapsack problem

• Matrix chain multiplication problem

• Edit distance problem

• Fractional knapsack problem