Recent questions tagged divide-and-conquer

Consider three recursive algorithms.Algorithm $\mathbf{1}$Divides a problem of size $N$ into two subproblems of size $N/2$ and performs constant additional work.$T_1(N)=2...

Randomized quicksort is applied to $n$ distinct keys, where $n$ is divisible by $16$.A pivot is chosen uniformly at random.What is the probability that both recursive sub...

Consider an array of $2n$ elements of the form:$1,2n-1,2,2n-2,3,2n-3,4,2n-4,\ldots,n,n$For example, when $n=8$:$1,15,2,14,3,13,4,12,5,11,6,10,7,9,8,8$What is the number o...

Consider the problem of sorting an array of $n$ comparable elements in which there are only four distinct keys.It is possible to design an algorithm that makes at most $4...

Why do $2$-pivot and $3$-pivot quicksort generally perform better than $1$-pivot quicksort?They always perform fewer comparisons. They always perform fewer exchanges. The...

In the worst case, approximately how many key comparisons and exchanges does the standard $\texttt{partition()}$ procedure perform on a subarray of length $n$?$\frac{n}{2...

The standard $2$-way quicksort partition procedure uses the first element as the pivot and stops both scans when they encounter an element equal to the pivot.It is applie...

Suppose $n$ elements are divided into groups of $r$ elements. The median of each group is found, and the median of these group medians is used as the selection pivot.For ...

An array contains $n\geq 8$ distinct elements:$a_1<a_2<\cdots<a_n$The array is sorted using randomized quicksort.What is the probability that $a_7$ and $a_8$ are compared...

Two sorted subarrays, each containing $n/2$ elements, are merged into one sorted array of length $n$.What is the possible range for the number of key comparisons made dur...

Assume that a merge sort 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...

There are $n$ cities, and exactly $k$ of them are contaminated. A test on any subset tells whether at least one contaminated city is present in that subset.A divide-and-c...

Initially, there are three sorted sequences:$(3,5), (7,9), (6)$They are merged by choosing sorted sequences from left to right using two-way merging.How many total key co...

A sorted table contains $2000$ distinct elements in increasing order. A key is searched using binary search, and it is guaranteed that the key exists in the table.What is...

Suppose instead of dividing the input into two parts, a modified merge sort divides the input into four equal parts, sorts each one-fourth recursively, and finally combin...

Merge sort divides an array of size $n$ into two halves, recursively sorts both halves, and then merges the two sorted halves.Which recurrence correctly represents merge ...

Karatsuba multiplication multiplies two $n$-digit numbers by reducing the number of recursive half-size multiplications.Which recurrence represents Karatsuba multiplicati...

An array has distinct elements. A local minimum is an element smaller than both of its neighbors, with endpoints compared to their only neighbor.A divide-and-conquer algo...

In the divide-and-conquer algorithm for maximum sum subarray, the maximum subarray may lie:entirely in the left half entirely in the right halfWhat is the third possible ...

Suppose array $A[1 \ldots n]$ is sorted in non-decreasing order and it is guaranteed that there exists an index $i$ such that:$A[i] = i$A divide-and-conquer algorithm che...

1. what is the space Complexity of efficient Quick sort algorithem for best case ? in a lecture Reddy Sir Said that it is O(1) is this correct  2.if in the gate exam if t...

Which of the following is not a divide and conquer methodBinary SearchMerge SortQuick SortHeap Sort

Which of the following statement(s) is/are true?(a) Quicksort and merge sort are both examples of divide and conquer algorithms.(b) If we randomly choose a pivot element ...

How To Solve This Using Divide And ConquerSuppose we are given the two n bit integers, assuming for common sense n as power of 2. It is required to multiply them using Di...