13
votes
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$ ...
10
votes
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,...
10
votes
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 ...
9
votes
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 ...
8
votes
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 ...
6
votes
Accepted
Closest pair of points in 3D
As you say, you can split the points in two sets $A$ and $B$ of roughly the same size, depending on whether their $x$ coordinate smaller than or at least some threshold $x_0$. Solve the problem ...
5
votes
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 ...
5
votes
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$, ...
D.W.♦
- 159k
5
votes
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 ...
4
votes
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 ...
3
votes
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$...
3
votes
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 ...
3
votes
Finding integer square root for large integers [find asymptotic time complexity]
Normally, you don't measure the complexity of a problem before designing an algorithm; instead, you measure the complexity of a particular algorithm. So, before you get to measuring complexity, the ...
D.W.♦
- 159k
3
votes
Strassen Algorithm for Unusal Matrices
Strassen's algorithm, when applied directly, only multiplies two square matrices of dimension $2^n$. You can use it to multiply two $m \times m$ matrices by finding the smallest power of 2 such that $...
3
votes
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 ...
3
votes
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 ...
3
votes
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 ...
3
votes
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 ...
3
votes
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 ...
3
votes
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 ...
3
votes
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 ...
3
votes
Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T
For a set $S = \{s_1,\dotsc,s_n\}$. Construct a polynomial $P(x): x^{s_1} + x^{s_2} + \dotsc + x^{s_n}$.
Multiply the polynomial by itself three times, i.e., $P(x) \cdot P(x) \cdot P(x)$. Let this ...
3
votes
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 ...
3
votes
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 ...
2
votes
Accepted
Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n
Your approach is almost correct, except for the fact that the upper limit of your summation should be $\log_2n$, rather than $n$. You should have
$$
T(n)=3^kT\left(\frac{n}{2^k}\right)+\left[n\left(\...
2
votes
Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n
You are correct that
$$
\begin{align*}
T(n) &= n + \tfrac{3}{2} n + (\tfrac{3}{2})^2 n + \cdots + (\tfrac{3}{2})^{k-1} n + 3^k T(n/2^k) \\ &=
n \sum_{t=0}^{k-1} (\tfrac{3}{2})^t + 3^k T(n/2^k) ...
2
votes
Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n
You have a mistake going from (2) to (3) because you lost $n$ and it is not clear why your sum should range from $i = 1$ to $i = n$ (it does not). Then it is not clear how you got from (3) to (4) ...
2
votes
Accepted
How do I find running time for the following divide and conquer problem?
You cannot use the Master Theorem to solve this recurrence, since $n!$ doesn't grow like $n^c$ for any $c$. Instead, Stirling's approximation shows that $n! \sim \sqrt{2\pi n} (n/e)^n$. Rather, expand ...
2
votes
Given an array of n unsorted integers, how can you check that any 2 elements within k distance of some element don't vary by a multiple of 2?
Yes, it can be done in $O(n \log k)$ time, using exactly the approach you hinted at.
You're going to do a linear scan over the array, from left to right. At each step, you check whether the max of ...
D.W.♦
- 159k
2
votes
Divide and Conquer majority element algorithm
It's not correct. On input [a a b c], the left side yields [a, 2], the right side yields ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
divide-and-conquer × 146algorithms × 90
recurrence-relation × 24
algorithm-analysis × 22
recursion × 20
time-complexity × 11
computational-geometry × 11
complexity-theory × 10
asymptotics × 8
sorting × 8
arrays × 8
master-theorem × 7
runtime-analysis × 5
dynamic-programming × 5
discrete-mathematics × 5
fast-fourier-transform × 5
mergesort × 4
graphs × 3
optimization × 3
reference-request × 3
proof-techniques × 3
correctness-proof × 3
matrices × 3
binary-search × 3
polynomials × 3