Complexity Analysis and Asymptotic Notations · Algorithms · GATE CSE

Let $T(n)$ be the recurrence relation defined as follows:$T(0) = 1$$T(1) = 2$, and$T(n) = 5T(n - 1) - 6T(n - 2)$ for $n \geq 2$Which one of the follow...

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

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?

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

Consider the following three functions. f1 = 10n, f2 = nlogn, f3 = n√n Which one of the following options arranges the functions in the increasing o...

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 equality $$\sum\limits_{i = 0}^n {{i^3}} = X$$ and the following choices for $$X$$ $$\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,...

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object in to a binary search tree of n nod...

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

Which of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

The worst case running time to search for an element in a balanced binary search tree with n2n elements is

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

Two alternate packages A and B are available for processing a database having 10k records. Package A requires 0.0001n2 time units and package B requir...

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

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 time complexity of computing the transitive closure of a binary relation on a set of elements is known to be:

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

Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

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

The maximum gate delay for any output to appear in an array multiplier for multiplying two n bit number is

The concatenation of two lists is to be performed on 0(1) time. Which of the following implementations of a list should be used?

Which of the following is false?

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

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

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

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers : $$T\left( n \right) = a.T\left( {\fra...

Consider the following recurrence relation. $$T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\\ {1\ \ \ \ \ \ \ if...

There are n unsorted arrays : A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, An contains n distinct elements. There are no common elements be...

The given diagram shows the flowchart for a recursive function $$A(n).$$ Assume that all statements, except for the recursive calls, have $$O(1)$$ tim...

An algorithm performs $${\left( {\log N} \right)^{1/2}}$$ find operations, N insert operations, $${\left( {\log N} \right)^{1/2}}$$ delete operations,...

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

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

The number of elements that can be stored in $$\Theta (\log n)$$ time using heap sort is

Which of the given options provides the increasing order of asymptotic Complexity of functions f1, f2, f3 and f4? f1 = 2n f2 = n3/2 f3(n) = $$n\,\log...

You are given the post order traversal, P, of a binary search tree on the n element, 1,2,....,n. You have to determine the unique binary search tree t...

Consider the following functions: F(n) = 2n G(n) = n! H(n) = nlogn Which of the following statements about the asymptotic behaviour of f(n), g(n), and...

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

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){ ...

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){ ...

In the following C function, let n $$ \ge $$ m. int gcd(n,m) { if (n % m == 0) return m; n = n % m; return gcd(m,n); } How many recursive calls are ma...

Consider the following C code segment: int IsPrime(n){ int i, n; for(i=2; i<=sqrt(n);i++){ if(n % i == 0){ printf("No prime\n"); return 0; ...

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

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two ...

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 +=...

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 +=...

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

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) + ...

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

What does the following algorithm approximate? (Assume m > 1, $$ \in > 0$$) x = m; y = 1; while(x - y > ε){ x = (x + y) / 2; y = m/x; } pr...

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

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 algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values: 1. Choose an i uniformly at...

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

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

$$\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 Hn = $$\sum\limits_{t = 1}^n {1/i,n \ge 1} $$ where T(n) satisfies the recurrence relation, T(n) = $${{n ...

What is the generating function G (z) for the sequence of Fibonacci numbers?

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