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

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?

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\limits_{k = 1}^j {A\left[ k \right]} $$. Determine the maximum of S(i, j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)

Answer : ________.

The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X⁵ + 4X³ + 6X + 5 for a given value of X using only one temporary variable is _____.

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

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

Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t₁ and t₂ be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following holds?

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

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 sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

The solution to the recurrence equation
T(2^k) = 3 T(2^k-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 randomized quicksort?

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 of the following statements is true?

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 of these elements after the second pass of the algorithm is:

A sorting technique is called stable if:

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 programs are efficient
III. The worst case complexity for Quicksort is O(n²)
IV. Binary search using a linear linked list is efficient.

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

Merge sort uses

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 always a child of the root node

III. A max-heap can be constructed from a binary search tree in Θ(n) time

IV. A binary search tree can be constructed from a max-heap in Θ(n) time

Which of the above statements are TRUE?

The number of possible min-heaps containing each value from $$\left\{ {1,2,3,4,5,6,7} \right\}$$ exactly once is _____.

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
      for k = j + 1 to n do
           D = D * 3

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)
            k = k + n/2;
    return k;
 }

The return value of the function is

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) {
      Dequeue(Q)
      m = m - 1
   }
}

What is the worst case time complexity of a sequence of n operations on an initially empty queue?

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

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}$$
Which one of the following represents the time complexity of the algorithm?

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?

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 elements. Let T(n) be the number of comparisons required to sort n elements. Then

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 following is TRUE about the number of comparisons needed?

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?

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?

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?

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

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
Let C₁ and C₂ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

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 input for which Quicksort takes maximum time.

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 t₁ and t₂ be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1], respectively. Which of the following holds?