Complexity of divide and conquer algorithm?

In summary, partitioning can be beneficial in certain cases, such as sorting, where it can reduce the time complexity of an algorithm. However, it is not a guaranteed solution and can sometimes result in more time being spent due to the cost of partitioning and reconstruction. Infinite recursion is also not always possible and should be carefully considered when using a divide and conquer approach.
  • #1
homomorphism
19
0
Let's say I have some algorithm with complexity [tex]O(n^k)[/tex] for some constant [tex]k[/tex]. and let's say it runs in some time [tex]T[/tex]. Now, I want to implement a divide and conquer approach for this algorithm, by dividing the problem in half each recursion. So basically, the first time i run my algorithm it will run in time [tex]T[/tex], the second time it will be [tex]O(\frac{n^k}{2^k}) + O(\frac{n^k}{2^k})[/tex] [since I'm running my algorithm on both halves] so the time will be [tex] \frac{T}{2^k} + \frac{T}{2^k}[/tex]. and then when i run my algorithm again it will be [tex]O(\frac{n^k}{4^k}) * 4[/tex]. This means the time will be [tex] 4 * \frac{T}{4^k} [/tex].

So basically, for a worst case scenario, with infinite recursions, I should have some sum,
[tex] \sum_{i=0}^{\infty} \frac{T}{2^i^{(k-1)}}[/tex]

Where [tex]T[/tex] is a constant. does this look about right?
 
Technology news on Phys.org
  • #2
bump...
 
  • #3
homomorphism said:
does this look about right?

You are doing several things wrong here. You are assuming that the problem at hand can be partitioned. This is not always the case. You are assuming that partitioning buys something, and this also is not always the case. Even if some problem can be partitioned and the partitioned problem is easier to solve, there is typically a cost involved in reconstructing the solution in terms of the original problem. Finally, you are assuming infinite recursion.

Consider a couple of examples: Multiplying a pair of square matrices and sorting a list.

Using conventional matrix multiplication algorithm to compute the product of a pair of NxN matrices requires N3 multiplications and N3-N2 additions; it is an O(n3) operation. Suppose the matrices are of size 2Nx2N. Each matrix can be split into four NxN submatrices. The product of the original matrices can be computed using these submatrices. Since 2x2 matrix multiplication requires 8 multiplications and 4 additions, the partitioned problem involves 8 NxN matrix multiplications and 4 NxN matrix additions, for a total of 8*N3=(2N)3 scalar multiplications and 8*(N3-N2)+4*N2=(2N)3-(2N)2 additions. Partitioning doesn't buy a thing here!

There exists a non-conventional technique for multiplying 2x2 matrices that requires but seven multiplications (but at the cost of extra bookkeeping and a lot of extra additions). Partitioning can be of benefit here. Infinite recursion is not possible; A 1x1 matrix cannot be split into smaller parts. For large matrices, this technique can be used to reduce the order from N3 to Nlog27.

Partitioning is the key tactic needed to make sorting an O(n*log(n)) problem rather than O(n2). However, the partitioning can only be carried so far (you can't split a list of one into parts) and the resulting sorted lists need to be merged.
 
  • #4
yeah, i definitely understand what you're saying. But for example, your matrix multiplication, let's say it runs in some time T. and then you partition it. the time it takes for the computation would be less right? (assuming it can be partitioned, you have a large enough matrix, etc), which is kind of what my formula above is trying to say (though you can modify the bounds of the summation depending on the situation). is this right?
 
  • #5
No. Partitioning the standard matrix multiplication algorithm doesn't buy a thing (the total number of multiplications and additions doesn't change.) In fact, it hurts because it takes time to perform the partitioning, extra time to do the extra bookkeeping the comes with partitioning, and extra time to reconstruct the solution from the partitioned products. Divide and conquer does not always work. Sometimes using divide-and-conquer costs more than just solving the original problem. Matrix multiplication is one case where this occurs. There are many, many others.
 

1. What is a divide and conquer algorithm?

A divide and conquer algorithm is a problem-solving approach where a complex problem is broken down into smaller subproblems that are easier to solve. These subproblems are then solved independently, and their solutions are combined to find the solution to the original problem.

2. How does a divide and conquer algorithm work?

A divide and conquer algorithm works by recursively dividing a problem into smaller subproblems until they become simple enough to solve directly. The solutions to the subproblems are then combined to find the solution to the original problem. This approach is often more efficient than solving the problem directly.

3. What are the advantages of using a divide and conquer algorithm?

One advantage of using a divide and conquer algorithm is that it can reduce the time complexity of solving a problem. By breaking a complex problem into smaller subproblems, the algorithm can solve each subproblem in less time and then combine the solutions to find the solution to the original problem. Additionally, divide and conquer algorithms are often easier to implement and debug.

4. What types of problems can be solved using a divide and conquer algorithm?

Divide and conquer algorithms can be used to solve a wide range of problems, including sorting, searching, and graph traversal. They are also commonly used in computer science and mathematics for problems such as matrix multiplication, finding the closest pair of points, and calculating the nth Fibonacci number.

5. Are there any limitations to using a divide and conquer algorithm?

While divide and conquer algorithms can be very efficient, they may not always be the best approach for solving a problem. In some cases, the subproblems may not be significantly simpler than the original problem, making the algorithm less efficient. Additionally, the process of dividing and combining solutions may require additional memory or resources, making the algorithm less practical for certain applications.

Similar threads

Replies
9
Views
942
  • Programming and Computer Science
Replies
1
Views
887
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
8
Views
971
  • Engineering and Comp Sci Homework Help
Replies
3
Views
897
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
3
Views
1K
Replies
15
Views
2K
  • Programming and Computer Science
Replies
31
Views
2K
  • Programming and Computer Science
Replies
4
Views
4K
Back
Top