# Complexity Analysis and Asymptotic Notations · Algorithms · GATE CSE

Start Practice## Marks 1

GATE CSE 2024 Set 2

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

GATE CSE 2024 Set 1

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

GATE CSE 2023

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?

GATE CSE 2022

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

GATE CSE 2022

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

GATE CSE 2020

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

GATE CSE 2015 Set 3

Consider the equality $$\sum\limits_{i = 0}^n {{i^3}} = X$$ and the following choices for $$X$$
$$\eqalign{
& \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,...

GATE CSE 2013

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

GATE CSE 2013

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

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 2012

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 of size n. Which of the follo...

GATE CSE 2010

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

GATE CSE 2007

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

GATE CSE 2006

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

GATE CSE 2005

The time complexity of computing the transitive closure of a binary relation on a set of elements is known to be:

GATE CSE 2003

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

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)
III. 22n = O(22n)
Which of those...

GATE CSE 2002

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 2001

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 1999

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

GATE CSE 1997

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

GATE CSE 1996

Which of the following is false?

## Marks 2

GATE CSE 2024 Set 1

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

GATE CSE 2023

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

GATE CSE 2021 Set 1

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

GATE CSE 2021 Set 1

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

GATE CSE 2019

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

GATE CSE 2016 Set 2

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

GATE CSE 2015 Set 3

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

GATE CSE 2015 Set 1

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

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 < n; ++i)
{
p = 0;
for...

GATE CSE 2013

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

GATE CSE 2011

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

GATE CSE 2008

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

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 the unique binary search tree t...

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 integers is

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 * f1(n - 2));
}
int f2(int n){
...

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 * f1(n - 2));
}
int f2(int n){
...

GATE CSE 2007

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

GATE CSE 2007

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

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);
}
How many recursive calls are ma...

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 = 0; i < n; i++){
sum +=...

GATE CSE 2005

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

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 = 0; i < n; i++){
sum +=...

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). Consider the following progr...

GATE CSE 2004

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

GATE CSE 2004

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

GATE CSE 2004

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

GATE CSE 2003

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

GATE CSE 2002

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

GATE CSE 2002

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

GATE CSE 2000

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

GATE CSE 1994

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

GATE CSE 1993

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

GATE CSE 1990

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

GATE CSE 1987

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?