1. Which of the following statements is/are true?

2. What will be the time complexity for the following recurrence relation?
T(n)=8T(n1/2)+(log n)2 if n>2
= 1,Otherwise

3. Which of the following cases does NOT exist while calculating time complexity?

4. Which of the following decision procedure has atleast doubly exponential time complexity?

5.

An unordered list contains n distinct elements. The number of comparisons to find an elements in the list that is larger than the second minimum in the list is

6. Consider the recurrence function Then T(n) in terms of Θ notation is

7. Consider the following C function.

int fun1(int n) {

int i, j, k, p, q = 0;

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

p = 0;

for (j = n; j > 1; j = j/2)

++ p;

for (k = 1; k<p; k = k*2)

++ q;

}

return q;

}

Which one of the following most closely approximates the return value of the function fun1?

8. Consider the following C function.

int fun(int n) {

int i, j;

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

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

printf (‘’ %d %d’’, i, j);

}

}

}

Time complexity of fun in terms of Θ notation is

9. Let f(n) = n and g(n) = n^{(1 + sin n)}, where n is a positive integer. Which of the following statements is/are correct?

I. f(n) = O(g(n))

II. f(n) = Ω(g(n))

10. Let f(n) = n and g(n) = n^{(1 + sin n)}, where n is a positive integer. Which of the following statements is/are correct?

I. f(n) = O(g(n))

II. f(n) = Ω(g(n))

11. There are n unsorted arrays: A₁, A₂, ..., An. Assume that n is odd. Each of A₁, A₂, ..., An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A₁, A₂, ..., A_n is

12. What is the complexity of the following code?

sum=0;

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

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

sum++;

13. For parameters a and b, both of which are ω(1), T(n) = T(n^1/a) + 1, and T(b) = 1.

Then T(n) is

14. In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a, b]? Assume that the number of reported elements is k.

15.

16. Consider the following recurrence relation.

Which one of the following option is correct?

17. An algorithm with three nested loops will have a Big-O efficiency of (a size on n).

18. The recurrence relation T(n) = 7T(n/7) + n has the solution:

19. Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

20. Consider the program

void function(int n) {

int i, j, count=0;

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

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

count++;

}

The complexity of the program is

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

f1(n) = 2n f2(n) = n3/2 f3(n) = n log2 n f4(n) = nlog2n

22. 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?

23. The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst-case time complexity of this function is O(nα), then the least possible (accurate up to two decimal position) of α is _______.

24. Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O(n^a log^b n). Then the value of a + 10b is _______

25.

Match the algorithms with their time complexities: