GATE CSE

Complexity Analysis and Asymptotic Notations

Algorithms

(Past Years Questions)

Marks 1

More
Consider the equality $$\sum\limits_{i = 0}^n {{i^3}} = X$$ and the following choices for $$X$$ $$\eqalign{ & \,\,\,...
GATE CSE 2015 Set 3
Which of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using ...
GATE CSE 2013
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object in to...
GATE CSE 2013
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
GATE CSE 2013
The worst case running time to search for an element in a balanced binary search tree with n2n elements is
GATE CSE 2012
Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input...
GATE CSE 2012
Two alternate packages A and B are available for processing a database having 10k records. Package A requires 0.0001n2 t...
GATE CSE 2010
Consider the following segment of C-code: int j, n; j=1; while(j The number of comparisons made in the execution of the...
GATE CSE 2007
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...
GATE CSE 2006
The time complexity of computing the transitive closure of a binary relation on a set of elements is known to be:
GATE CSE 2005
Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total ...
GATE CSE 2003
Consider the following three claims I. (n + k)m = $$\Theta \,({n^m})$$ where k and m are constants II. 2n+1 = O(2n) II...
GATE CSE 2003
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
GATE CSE 2002
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?...
GATE CSE 2001
The maximum gate delay for any output to appear in an array multiplier for multiplying two n bit number is
GATE CSE 1999
The concatenation of two lists is to be performed on 0(1) time. Which of the following implementations of a list should ...
GATE CSE 1997
Which of the following is false?
GATE CSE 1996

Marks 2

More
The given diagram shows the flowchart for a recursive function $$A(n).$$ Assume that all statements, except for the recu...
GATE CSE 2016 Set 2
Let $$f\left( n \right) = n$$ and $$g\left( n \right) = {n^{\left( {1 + \sin \,\,n} \right)}},$$ where $$n$$ is a positi...
GATE CSE 2015 Set 3
An algorithm performs $${\left( {\log N} \right)^{1/2}}$$ find operations, N insert operations, $${\left( {\log N} \righ...
GATE CSE 2015 Set 1
Consider the following C function. int fun1 (int n) { int i, j, k, p, q = 0; for (i = 1; i 1; j = j/2) ...
GATE CSE 2015 Set 1
The number of elements that can be stored in $$\Theta (\log n)$$ time using heap sort is
GATE CSE 2013
Which of the given options provides the increasing order of asymptotic Complexity of functions f1, f2, f3 and f4? f1 = 2...
GATE CSE 2011
Consider the following functions: F(n) = 2n G(n) = n! H(n) = nlogn Which of the following statements about the asymptoti...
GATE CSE 2008
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n...
GATE CSE 2008
You are given the post order traversal, P, of a binary search tree on the n element, 1,2,....,n. You have to determine t...
GATE CSE 2008
Consider the following C functions: int f1(int n){ if(n == 0 || n == 1){ return n; } return (2 * f1(n - 1) + 3 * ...
GATE CSE 2008
Consider the following C functions: int f1(int n){ if(n == 0 || n == 1){ return n; } return (2 * f1(n - 1) + 3 * ...
GATE CSE 2008
What is the time complexity of the following recursive function? int DoSomething(int n){ if(n ...
GATE CSE 2007
Consider the following C code segment: int IsPrime(n){ int i, n; for(i=2; i Let T(n) denote the number of times the fo...
GATE CSE 2007
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); } H...
GATE CSE 2007
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is gi...
GATE CSE 2005
Consider the following C - function: double foo(int n){ int i; double sum; if(n == 0) return 1.0; sum = 0.0; for (i...
GATE CSE 2005
Consider the following C - function: double foo(int n){ int i; double sum; if(n == 0) return 1.0; sum = 0.0; for (i...
GATE CSE 2005
What does the following algorithm approximate? (Assume m > 1, $$ \in > 0$$) x = m; y = 1; while(x - y > ε){ x = (...
GATE CSE 2004
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)...
GATE CSE 2004
The time complexity of the following C function is (assume n > 0) int recursive(int n){ if(n == 1){ return (1); } ...
GATE CSE 2004
The recurrence equation T(1) = 1 T(n) = 2T(n - 1)+n, $$n \ge 2$$ Evaluates to
GATE CSE 2004
The cube root of a natural number n is defined as the largest natural number m such that $${m^3} \le n$$. The complexity...
GATE CSE 2003
Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct value...
GATE CSE 2002
The running time of the following algorithm Procedure A(n) If n...
GATE CSE 2002
Consider the following functions $$f(n) = 3{n^{\sqrt n }}$$ $$g(n) = {2^{\sqrt n {{\log }_2}n}}$$ $$h(n) = n!$$ Which of...
GATE CSE 2000
Conside the following two functions: $${g_1}(n) = \left\{ {\matrix{ {{n^3}\,for\,0 \le n $${g_2}(n) = \left\{ {\matr...
GATE CSE 1994
$$\sum\limits_{1 \le k \le n} {O(n)} $$ where O(n) stands for order n is:
GATE CSE 1993
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 recu...
GATE CSE 1990
Solve the recurrence equations T (n) = T (n - 1) + n T (1) = 1
GATE CSE 1987
What is the generating function G (z) for the sequence of Fibonacci numbers?
GATE CSE 1987

EXAM MAP

Graduate Aptitude Test in Engineering

GATE ECE GATE CSE GATE CE GATE EE GATE ME GATE PI GATE IN

Joint Entrance Examination

JEE Main JEE Advanced