# Tag Info

## Hot answers tagged divide-and-conquer

### Strassen algorithm for matrix multiplication complexity analysis

It's true that the parameter $n$ usually denotes the size of the input, but this is not always the case. For square matrix multiplication, $n$ denotes the number of rows (or columns). For graphs, $n$ ...
• 268k

### Show how to do FFT by hand

Define the polynomials, where deg(A) = q and deg(B) = p. The deg(C) = q + p. In this case,...
• 101
Accepted

### Divide and Conquer to identify a knight from n people

An efficient algorithm using stack Initialize an empty stack. For each person $p$ in the given people: If the stack is empty, push $p$ to the stack. Otherwise, pit $p$ against the person at the top ...
• 32.9k
Accepted

### Categorization of Binary search as Divide and Conquer

This might seem silly but here we go. Let our array be $A$ and the current range we are searching in be denoted as $[L,R]$ and let $mid = \frac{L+R}{2}$. The divide step - We divide our search ...
• 1,168

### Divide and Conquer to identify a knight from n people

Our princess proceeds as follows: she asks her suitors to form up on a line starting from the left, she asks each person about the virtue of their neighbour (and vice versa) if there is an ...
• 529
Accepted

### Sums of all pairs: possible less than quadratic?

Yes, it is possible using $O(n \log n)$ preprocessing and $O(\log n)$ query time. Given the set $S$, construct the polynomial $P(x)=\Sigma_{s\in S}\textrm{ } x^s$. Then use the FFT multiplication ...

### Categorization of Binary search as Divide and Conquer

There is no accepted formal definition of the divide and conquer paradigm (see this question for some suggestions), and so we must regard this paradigm as an informal concept. The main idea in divide ...
• 268k
Accepted

### Counting Total Number of Non-Equivalent Configurations in a 2-D Grid

We will use Burnside's lemma, plus some additional optimizations. Note that row swaps and column swaps commute, so the group of allowable transformations to the grid is exactly $G = S_w \times S_h$, ...
• 140k

### Strassen algorithm for matrix multiplication complexity analysis

It's back to the size of the matrix. Suppose the original matrix is $n\times n$. Hence we will consider $T(n)$ as a computation of two matrix with size of $n\times n$. When we divide the original ...
• 3,497
Accepted

### Just another Divide-And-Conquer question - but somehow different

Your solution doesn't work since it could output $i_2,j_1$ which isn't legal since $i_2 > j_1$. Your code also has a few bugs — are you returning indices or stock prices? The idea behind the ...
• 268k

### Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

$X_m$ and $Y_m$ are not shaded, because each of them is potentially the median of $X \cup Y$. Consider two examples (Below I take the $\lfloor (n+1)/2 \rfloor$-th element as the median of an array ...
• 9,179
Accepted

### Exercise on Divide&Conquer's technique

Given an array of elements $a[i], 0\le i\le n-1$, we know we can sort it in time $O(n\log n)$. Then do the following to produce an array $b[\;]$: ...
• 14.5k
Accepted

### Justifying a claim in the proof of the master theorem

Suppose that $f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants $N,C>0$ such that $f(n) \leq Cn^{\log_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the ...
• 268k
Accepted

### Understanding Closest Pair Algorithm (CLRS)

Assume that a point exists in every corner in the figure (including the inside corners). If points cannot overlap, then you have 6 points that can reside in the 𝛿x2𝛿 box, and since you must be ...
• 46
Accepted

### Can Strassen's multiplication algorithm be improved if we divide matrices to 3x3 or axa in general?

There is nothing special about 2×2 matrices. In fact you can do much better using larger matrices. The reason that you are only being explained the 2×2 algorithm is that it is simple to describe. The ...
• 268k

### Algorithm in O(logn)

This can be viewed as an array with indices given by $1,2,3,\dots,n$ such that $f(i)$ is stored at index $i$. As $f(i)$ is monotonic, and the sign changes from positive to negative with increasing $i$...
• 853

### Strassen Algorithm for Unusal Matrices

Almost the same as Yuval's answer, except... If I gave you two 1025 x 1025 matrices, you wouldn't extend them to 2048 x 2048. You'd extend them to 1026 x 1026, and use one layer of Strassen's ...
• 24.9k
Accepted

### Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$

If we are not restricted by "using the master theorem", then either a better version of the master theorem, the versatile Akra-Bazzi method or the elementary way to show many recurrence relations mean ...
• 32.9k
Accepted

### Applications of divide-and-conquer outside of merge sort and quicksort

There are many algorithms that uses the divide-and-conquer paradigm besides merge sort and quicksort. "There is no accepted formal definition of the divide and conquer paradigm, and so we must regard ...
• 32.9k
Accepted

### Difference between sequential and parallel divide and conquer

Just like you wrote, you can solve independent subproblems in parallel. Here are two examples: In merge sort, you can sort the two halves of the input in parallel, and then merge them together ...
• 268k

### How to understand the recurrence relation and time-complexity of StoogeSort?

Here are some more hints: The algorithm partitions the array $A$ into three parts $B,C,D$ such that $|C| \geq |B|,|D|$ and then sorts $BC$ (the array formed by the first two parts), $CD$ (the array ...
• 268k

### Converting a greedy algorithm to a dynamic programming algorithm

The example you specified is not turning a greedy algorithm to a dynamic programming solution. You reduced a problem to another using a greedy argument and solved the other problem using dynamic ...
• 4,073

### Clarification on the algorithm for finding a majority element

The algorithm as written assumes that $n$ is a power of 2. But you can adjust it to support odd-length arrays, while still completing in $O(n)$ time, as follows: Suppose that at some given point in ...
• 268k

### Algorithms question: Largest contiguous subset selection

O(n) solution: Move index j from left to right and drag i behind so that the window from i ...
• 178

### Divide and Conquer to identify a knight from n people

This can be solved efficiently with the Boyer-Moore majority algorithm. Everyone casts a vote on the candidate currently occupying the hot seat. When the count reaches zero, the candidate is evicted ...
• 674

### $O(n \log n)$ simple polygon triangulation via divide and conquer

Garey, Johnson, Preparata and Tarjan came up with a simple $O(n\log n)$ algorithm back in 1978. It is described in many lecture notes, for example these lecture notes of Piotr Indyk.
• 268k

### How many times can you divide a list of n elements in 1/2

You haven't explained what "divide in half" means, but let's assume that it means to divide the list into two halves of as equal size as possible (equal if the number of elements is even, almost equal ...
• 268k
Accepted

### Help needed with lesson on recursion

Here are several approaches to compute $x^n$ from smaller powers of $x$: doing $x \times x^{n-1}$. The former is $P(1)$ the latter is $P(n-1)$. doing $x^2 \times x^{n-2}$. The former is $P(2)$, the ...
• 20.3k
The paper explains why the number of comparisons is $O(n)$ in the next few sentences immediately after the statement you're asking for a justification of. Just keep reading for a few more sentences, ...
Hint: Define $B[i] = A[i] - i$. What can you say about the array $B$? Use the fact that $A$ contains distinct integers.