time-complexity

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

An undirected, unweighted, simple graph $G(V, E)$ is said to be 2 -colorable if there exists a function $c: V \rightarrow\{0,1\}$ such that for every $(u, v) \in E, c(u) \neq c(v)$...

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

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

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst case time...

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. $\fora...

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n distinct integers?

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures: P: Unsorted doubly...

Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct. We wi...

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?

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures: P: Unsorted doubly...

Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct. We wi...

An array $A$ of length $n$ with distinct elements is said to be bitonic if there is an index $1=i=n$ such that $A[1 . . i]$ is sorted in the non-decreasing order and $A[i+1 . . n]$...

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

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

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

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

Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function th...

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?

Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation EXTRACT-MAX(A) extracts and deletes the maximum...

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

A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?

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

Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

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

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

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

Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u, v) $$ \in $$ V $$ \t...

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

What is the worst case time complexity of inserting n 2 elements into an AVL-tree with n elements initially?

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

Match the algorithms with their time complexities: Algorithm (P) Towers of Hanoi with n disks (Q) Binary search given n sorted numbers (R) Heap sort given n numbers at the worst ca...

A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two externa...

Consider the following C function. ```c 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...

An operator $$delete(i)$$ for a binary heap data structure is to be designed to delete the item in the $$i$$-th node. Assume that the heap is implemented in an array and i refers t...

Consider a carry lookahead adder for adding two $$n$$-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT ($$n$$ refers to the numb...

$$N$$ items are stored in a sorted doubly linked list. For a $$delete$$ operation, a pointer is provided to the record to be deleted. For a $$decrease$$-$$key$$ operation, a pointe...

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE ? $$\,\,\,\,\,\,...

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

Consider a complete binary tree where the left and the right sub-trees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( $$ \ge 2$$ ) numbers? In the recurrence equation...

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

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

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

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

Assume that a mergesort algorithm in the worst case takes $$30$$ seconds for an input of size $$64.$$ Which of the following most closely approximates the maximum input size of a p...

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there...

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 O(n a Log b n...

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

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case...

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

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

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

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

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

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation 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 following is ALWAYS TRUE?

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

What is the number of swaps required to sort n elements using selection sort, in the worst case?

In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

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

Which of the following is TRUE?

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 Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the...

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,..........., n. You have to determine the unique binary search tree that has P as its posto...

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

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 that has P as its post order tr...

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this 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){ int i; int X[N], Y[N], Z[N]; X[0] = Y[...

Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compu...

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); }

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 made by this function?

Which of the following sorting algorithms has the lowest worst-case complexity?

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:

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the...

The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

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?

Given two arrays of numbers a 1 ,......,a n and b 1 ,......, b n where each number is 0 or 1, the fastest algorithm to find the largest span (i, j) such that a i +a i+1 ......a j =...

In a binary max heap containing n numbers, the smallest element can be found in time

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node does not satisfy the heap proper...

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

Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time compl...

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

Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \over {\log n}}} \right\rfloor $$ elements each. The time complexity of producing a sorted list of all...

Two matrices M 1 and M 2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The tim...

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 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 tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

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

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

Let P be a singly linked list, Let Q be the pointer to an intermediate node x in the list.What is the worst-case time complexity of the best known algorithm to delete the node x fr...

In a heap with n elements with the smallest element at the root, the 7 th smallest element can be found in time

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

The usual $$\Theta ({n^2})$$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorte...

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element 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

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

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

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

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?

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

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

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

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

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?

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

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

For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of

The recurrence relation that arises in relation with the complexity of binary search is:

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

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is _______.

Following algorithm(s) can be used to sort n integers in the range [1....... n 3 ] in O(n) time

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and m edges has the time complexity of:

Match the pairs in the following: List - I (a) Heap construction (b) Constructing hash table witn linear probing (c) AVL Tree construction (d) Digital tree construction List - II (...

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

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

Let P be a quicksort program to sort numbers in ascending order. Let t 1 and t 2 be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1], respectively. Which of t...