Complexity Theory

Consider the recursive functions represented by the following code segment: int bar(int n){ if (n == 1) return 0; else return 1 + bar(n/2); } int foo(int n){ if (n == 1) return 1; else return 1 + foo(bar(n)); } The small...

Consider an array $A$ of integers of size $n$. The indices of $A$ run from 1 to $n$. An algorithm is to be designed to check whether $A$ satisfies the condition given below. $\forall i, j \in\{1, \ldots, n-1\}$ such that...

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$ ?

Consider the following functions, where $n$ is a positive integer. $$ n^{1 / 3}, \log (n), \log (n!), 2^{\log (n)} $$ Which one of the following options lists the functions in increasing order of asymptotic growth rate?...

Consider the following recurrence relations: For all $n>1$, $$ \begin{aligned} & T_1(n)=4 T_1\left(\frac{n}{2}\right)+T_2(n) \\ & T_2(n)=5 T_2\left(\frac{n}{4}\right)+\theta\left(\log _2 n\right) \end{aligned} $$ Assume...

Consider the following recurrence relation : $$T(n)=2 T(n-1)+n 2^n \text { for } n>0, T(0)=1$$ Which ONE of the following options is CORRECT?

Consider the following C program : #include <stdio.h> int g(int n) { return (n+10); } int f(int n) { return g(n*2); } int main() { int sum, n; sum=0; for (n=1; n The output of the given C program is ________. (Answer in...

Given an integer array of size $N$, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element...

Consider the following C program: #include &ltstdio.h> int main() { int a = 6; int b = 0; while(a Which one of the following statements is CORRECT?

Consider the following C function definition. int f(int x, int y) { for (int i=0; i<y; i++) { x=x+x+y; } return x; } Which of the following statements is/are TRUE about the above function?

Consider the following recurrence relation: $$T(n) = \begin{cases} \sqrt{n} T(\sqrt{n}) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases}$$ Which one of the following options is CORRECT?

Let $$f$$ and $$g$$ be functions of natural numbers given by $$f(n)=n$$ and $$g(n)=n^2$$. Which of the following statements is/are TRUE?

Consider functions Function_1 and Function_2 expressed in pseudocode as follows: Function 1 while n > 1 do for i = 1 to n do x = x + 1; end for n = n/2; end while Function 2 for i = 1 to 100 ∗ n do x = x + 1; end for L...

Which one of the following statements is TRUE for all positive functions f(n) ?

Consider the following recurrence : f(1) = 1; f(2n) = 2f(n) $$-$$ 1, for n $$\ge$$ 1; f(2n + 1) = 2f(n) + 1, for n $$\ge$$ 1; Then, which of the following statements is/are TRUE?

Consider the following ANSI C program #include <stdio.h> int foo(int x, int y, int q) { if ((x <= 0 && (y <= 0)) return q; if (x <= 0) return foo(x, y - q, q); if (y <= 0) return foo(x - q, y, q); return foo (x, y - q, q...

Consider the following three functions. f 1 = 10 n , f 2 = n logn , f 3 = n √n Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers : $$T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)$$ Which one of the following options is co...

Consider the following ANSI C program. #include <stdio.h> int main( ) { int i, j, count; count = 0; i = 0; for (j = -3; j = 0) && (i++)) count = count + j; } count = count + i; printf("%d", count); return 0; } Which one...

Consider the following recurrence relation. $$T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\\ {1\ \ \ \ \ \ \ if\ n = 0} \end{array}} \right.$$ Which one of the following option is corre...

For parameters a and b, both of which are $$\omega \left( 1 \right)$$, T(n) = $$T\left( {{n^{1/a}}} \right) + 1$$, and T(b) = 1. Then T(n) is

Consider the following C function. void convert(int n){ if(n < 0) printf("%d",n); else { convert(n/2); printf("%d",n%2); } } Which one of the following will happen when the function convert is called with any positive in...

There are n unsorted arrays : A 1 , A 2 , …, A n . Assume that n is odd. Each of A 1 , A 2 , …, A n contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of com...

Consider the following C program : #include <stdio.h> int main(){ float sum = 0.0, j = 1.0, i = 2.0; while (i/j > 0.0625){ j = j + j; sum = sum + i/j; printf("%f\n", sum); } return 0; } The number of times the variable s...

Consider the following C program: #include < stdio.h > int jumble (int x, int y) { x = 2 * x + y ; return x ; } int main ( ) { int x=2, y=5 ; y = jumble (y, x) ; x = jumble (y, x) ; printf ("%d \n", x) ; return 0 ; } The...

Consider the following C code. Assume that unsigned long int type length is 64 bits. unsigned long int fun(unsigned long int n){ unsigned long int i, j = 0, sum = 0; for (i = n; i > 1; i = i/2) j++; for ( ; j > 1; j = j/...

Consider the following C program: #include < stdio.h > int counter = 0; int calc (int a, int b) { int c; counter++; if (b==3) return (a*a*a); else { c = calc(a, b/3); return (c*c*c); } } int main (){ calc(4, 81); printf...

Consider the following functions from positive integers to real numbers : $10, \sqrt{n}, n, \log _2 n, \frac{100}{n}$. The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is :

Consider the following C program segment. while(first <= last) { if (array[middle] < search) first = middle + 1; else if (array[middle] == search) found = TRUE; else last = middle - 1; middle = (first + last)/2; } if (fi...

Which one of the following assertions concerning code inspection and code walk-through is true?

Consider the following C function. int fun ( int n ) { int x = 1, k ; if ( n == 1) return x ; for( k = 1 ; k < n ; ++ k ) x = x + fun( k ) * fun( n - k ) ; return x ; } The return value of fun (5) is ________.

Consider the following pseudo code, where x and y are positive integers. begin q := 0 r := x while r ≥ y do begin r := r - y q := q + 1 end end The post condition that needs to be satisfied after the program terminates i...

Consider a software project with the following information domain characteristics for calculation of function point metric. Number of external inputs $$\left( {\rm I} \right) = 30$$ Number of external outputs $$\left( O...

Consider the equality $$\sum\limits_{i = 0}^n {{i^3}} = X$$ and the following choices for $$X$$ $$\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^4}} \right) \cr & \,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\Th...

Consider two decision problems $${Q_1},{Q_2}$$ such that $${Q_1}$$ reduces in polynomial time to $$3$$-$$SAT$$ and $$3$$-$$SAT$$ reduces in polynomial time to $${Q_2}.$$ Then which one of the following is consistent with...

An unordered list contains $$n$$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

Let $$f\left( n \right) = n$$ and $$g\left( n \right) = {n^{\left( {1 + \sin \,\,n} \right)}},$$ where $$n$$ is a positive integer. Which of the following statements is/are correct? $$\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,...

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 m...

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(1) = 2T (n/2) + log n

Consider the following function double f (double x) { if ( abs (x * x – 3) < 0. 01) return x; else return f (x / 2 + 1.5/x); } Give a value q (to 2 decimals) such that f(q) will return q:______.

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P,...

Consider the decision problem 2CNFSAT defined as follows: { $$\Phi $$ | $$\Phi $$ is a satisfiable propositional formula in CNF with at most two literal per clause} For example, $$\Phi = \left( {{x_1} \vee {x_2}} \right)...

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

The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X 5 + 4X 3 + 6X + 5 for a given value of X using only one temporary variable is _____.

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; } The return value of the function is

Which of the following statements are TRUE? 1. The problem of determining whether there exists a cycle in an undirected graph is in P. 2. The problem of determining whether there exists a cycle in an undirected graph is...

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty and m > 0) { Dequeue(Q) m = m - 1 } } What is the worst ca...

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?

What will be the output of the following C program segment? Char inchar = 'A'; Switch ( inchar ) { case 'A' : printf ("Choice A\ n") ; case 'B' : case 'C' : printf (“Choice B”) ; case 'D' : case 'E' : default : printf (...

Which of the given options provides the increasing order of asymptotic Complexity of functions f 1 , f 2 , f 3 and f 4 ? f 1 = 2 n f 2 = n 3/2 f 3 (n) = $$n\,\log _2^n$$ f 4 (n) = n log 2 n

A company need to develop digital signal processing software for one of its newest inventions. The software is expected to have $$4000$$ lines of code. The company needs to determine the effort in person months needed to...

Consider the following recursive C function that takes two arguments: unsigned int foo (unsigned int n, unsigned int r) { if (n > 0) return((n % r) + foo(n/r, r)); else return 0; } What is the return value of the functio...

Two alternate packages A and B are available for processing a database having 10 k records. Package A requires 0.0001n 2 time units and package B requires $$10n.\log _{10}^n$$ time units to process n records. What is the...

The following program is to be tested for statement coverage: begin if $$\left( {a = \,\, = b} \right)\,\,\left\{ {S1;\,\,exit;} \right\}$$ else if $$\left( {c = \,\, = d} \right)\,\,\left\{ {S2;} \right\}$$ else $$\left...

The running time of an algorithm is represented by the following recurrence relation: $$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$$ Which one of the following represents the...

Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE? $${\rm I}.\,\,\,\,\,\,$$ The cyclomatic complexity of a module is equal to the max...

Consider the following functions: F(n) = 2 n G(n) = n! H(n) = n logn Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

Consider the following C functions: int f1(int n){ if(n == 0 || n == 1){ return n; } return (2 * f1(n - 1) + 3 * f1(n - 2)); } int f2(int n){ int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1]...

The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to W. An algorithm Q solves this problem in O(nW) t...

When $$n = {2^{2k}}$$ for some $$k \ge 0$$, the recurrence relation $$$T\left( n \right) = \sqrt 2 T\left( {n/2} \right) + \sqrt n ,\,\,T\left( 1 \right) = 1$$$ evaluates to

What is the time complexity of the following recursive function? int DoSomething(int n){ if(n <= 2) return 1; else return (floor(sqrt(n)) + n); }

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:

Let SHAM 3 be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM 3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is...

Consider the polynomial $$P\left( x \right) = {a_0} + {a_1}x + {a_2}{x^2} + {a_3}{x^3},$$ where $${a_i} \ne 0,\forall i$$. The minimum number of multiplications needed to evaluate $$p$$ on an input $$x$$ is

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. Whi...

Consider the following recurrence: $$T\left( n \right){\rm{ }} = {\rm{ 2T(}}\left\lceil {\sqrt n } \right\rceil {\rm{) + }}\,{\rm{1 T(1) = 1}}$$ Which one of the following is true?

Consider the following C - function: double foo(int n){ int i; double sum; if(n == 0) return 1.0; sum = 0.0; for (i = 0; i < n; i++){ sum += foo(i); } return sum; } The space complexity of the above function is:

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is FALSE?

Let A[1,...,n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is O(m). Consider the following program fragment written in a C like language: counter = 0; for(i = 1; i <=...

The recurrence equation T(1) = 1 T(n) = 2T(n - 1)+n, $$n \ge 2$$ Evaluates to

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{ no. of leaf-nodes in left-subtree of x, no. of lea...

The time complexity of the following C function is (assume n > 0) int recursive(int n){ if(n == 1){ return (1); } return (recursive(n - 1) + recursive(n - 1)); }

The goal of structured programming is to

The cube root of a natural number n is defined as the largest natural number m such that $${m^3} \le n$$. The complexity of computing the cube root of n (n is represented in binary notation) is

Consider the following three claims I. (n + k) m = $$\Theta \,({n^m})$$ where k and m are constants II. 2 n+1 = O(2 n ) III. 2 2n = O(2 2n ) Which of those claims are correct?

The solution to the recurrence equation T(2 k ) = 3 T(2 k-1 ) + 1, T (1) = 1, is:

The running time of the following algorithm Procedure A(n) If n<=2 return (1) else return (A([$$\sqrt n $$])); is best described by

Consider the following C program: void abc(char *s) { if(s[0]=='\0') return; abc(s+1); abc(s+1); printf("%c",s[0]); } main() { abc("123"); } (a) What will be the output of the program? (b) If abc(s) is called with a null...

Let f(n) = n 2 log n and g(n) = n(log n) 10 be two positive functions of n. Which of the following statements is correct?

Consider the following functions $$f(n) = 3{n^{\sqrt n }}$$ $$g(n) = {2^{\sqrt n {{\log }_2}n}}$$ $$h(n) = n!$$ Which of the following is true?

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?

Consider the following C function definition int Trial (int a, int b, int c) { if ((a > = b) && (c < b)) return b; else if (a > = b) return Trial (a,c,b); else return Trial (b,a,c); } The function Trial:

If T 1 = O(1), give the correct matching for the following pairs: List - I (M) T n = T n - 1 + n (N) T n = T n/2 + n (O) T n = T n/2 + nlog n (P) T n = T n - 1 + log n List - II (U) T n = O(n) (V) T n = O(nlogn) (W) T n...

Give the correct matching for the following pairs: Group - 1 (A) $${\rm O}(\log n)$$ (B) $${\rm O}(n)$$ (C) $${\rm O}(n\log n)$$ (D) $${\rm O}({n^2})$$ Group - 2 (P) Selection (Q) Insertion sort (R) Binary search (S) Mer...

What value would the following function return for the input x = 95? Function fun (x:integer):integer; Begin If x > 100 then fun : x – 10 Else fun : fun(fun (x + 11)) End;

What value would the following function return for the input x = 95? function fun (x:integer):integer; Begin If x > 100 then fun : x – 10 Else fun : fun(fun (x + 11)) End;

Let T(n) be the function defined by $$T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$$ Which of the following statements is true?

The recurrence relation T(1) = 2 T(n) = 3T(n/4) + n has the solution, T(n) equals to

Which of the following is false?

The recurrence relation $$\,\,\,\,\,$$ $$T\left( 1 \right) = 2$$ $$T\left( n \right) = 3T\left( {{n \over 4}} \right) + n$$ has the solution $$T(n)$$ equal to

Conside the following two functions: $${g_1}(n) = \left\{ {\matrix{ {{n^3}\,for\,0 \le n < 10,000} \cr {{n^2}\,for\,n \ge 10,000} \cr } } \right.$$ $${g_2}(n) = \left\{ {\matrix{ {n\,for\,0 \le n \le 100} \cr {{n^3}\,for...

An unrestricted use of the "goto" statement is harmful because

What does the following code do? var a, b : integer; begin a:=a+b; b:=a-b; a:=a-b; end;

$$\sum\limits_{1 \le k \le n} {O(n)} $$ where O(n) stands for order n is:

Express T(n) in terms of the harmonic number H n = $$\sum\limits_{t = 1}^n {1/i,n \ge 1} $$ where T(n) satisfies the recurrence relation, T(n) = $${{n + 1} \over 2}$$ T(n-1) + 1, for $$n \ge 2$$ and T(1) = 1 What is the...

An unrestricted use of the "goto" statement is harmful because of which of the following reason(s):

Solve the recurrence equations: $$\,\,\,\,\,\,\,\,\,\,T\left( n \right) = \left( {{n \over 2}} \right) + 1$$ $$\,\,\,\,\,\,\,\,\,\,\,T\left( 1 \right) = 1$$

Find a solution to the following recurrence equation T(n) = T(n - 1)+ n T(1) = 1

Solve the recurrence equations T (n) = T (n - 1) + n T (1) = 1