Divide and Conquer Method · Algorithms · GATE CSE

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

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

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

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum $$S\left( {i,j} \right) = \sum\limit...

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

The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X5 + 4X3 + 6X + 5 for a given value of X using only one tempora...

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

Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P...

Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one...

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

The solution to the recurrence equation T(2k) = 3 T(2k-1) + 1, T (1) = 1, 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 ran...

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

A sorting technique is called stable if:

If one uses straight two-way merge sort algorithm to sort the following elements in ascending order 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 then the order...

Which of the following statements is true? I. As the number of entries in a hash table increases, the number of collisions increases. II. Recursive pr...

Merge sort uses

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

Consider the following statements: I. The smallest element in a max-heap is always at a leaf node II. The second largest element in a max-heap is a...

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

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers 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...

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. MultiDequeue(Q){ m = k whil...

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

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

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

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

An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of 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 selec...

Consider the following recurrence: $$T\left( n \right){\rm{ }} = {\rm{ 2T(}}\left\lceil {\sqrt n } \right\rceil {\rm{) + }}\,{\rm{1 T(1) = 1}}$$ Wh...

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

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?

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot i) 1, 2, 3,......., n ii) n, n-1, n-2,......, 2, 1...

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

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

Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…n] are to be sorted, give an...

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

Let P be a quicksort program to sort numbers in ascending order. Let t1 and t2 be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 ...