Why we usually divide in two parts in divide and conquer algorithms?

Question

In merge sort we divide in two parts while solving . Why we didn't divided it in 3 or more parts ? Similarly in many divide and conquer problems I have seen one tend to divide in two parts . Why not 3 or more parts ? What impact would it have on solution / complexity ?

Answer 1

You can. But it would not matter that much. Dividing yields a complexity of log (let's talk about it very generally).

To be precise you get log_2 but it is generalized to log because constant factors don't matter in complexity analysis (Big-O-Notation, Wikipedia). And you can always transform a log_a into a log_b by only using a constant factor:

log_a(x) = log_b(x) * (1 / log_b(a))

On a more specific level you get a constant factor of 2 somewhere when splitting into two halves. If you now split into 4 you'll substitute that 2 but that's actually just a constant factor change, in any case.

---

Actually splitting into more than two parts is often done in practice when using parallel or distributed programming.

But besides of that divide and conquer is simply a technique which makes problems easier to understand for humans. You transform a harder problem into small easier problems.

Most times the only benefit of divide and conquer will be that it is more easy to understand.

Answer 2

Dividing the problem in 3 or more parts is usually inconvenient and has no effect on the algorithmic complexity. It will usually impact real-world performance negatively because more complicated code tends to be less efficient in practice than simple streamlined code. But this is not always the case.

There are a few practical D&C algorithms that divide the problem in more than two parts because it's beneficial to do so. The dual-pivot quicksort is one example. It tends to be somewhat faster (by a constant factor) than the regular quicksort.

Answer 3

Because implementation complexity versus time complexity tradeoffs.

Lets understand it through an example and how "divide" works. Lets say we have n elements, on which we have to perform some algorithm. Lets see the difference in linear and log complexities.

Say, for example, n~10^6, then any linear function on the data-set would take about 10^6 * t units of time, where t is time spent on processing one data point. For a divide and conquer approach, this reduces to log(10^6) * t units of time. This varies on the value of base of log, which in divide and conquer algorithms, are just the number of "parts" we divide our dataset into.

Lets look at the numbers for log for different bases.

   base                log 10^6 in base

    2                   20
    3                   12.6
    4                   10

etc.

So, we can see that dividing in more parts doesn't actually decrease time by that much, because for like 10^6 elements in data set, you make 20 iterations or 12 or 10, it doesn't make a difference, but compare it to 10^6 (O(n)-complex), there you see it.

Now, lets see what happens if we divide into 3 parts and work with it. Its implementation is a lot more complex than working with 2 parts. We are not able to achieve any significant time drops but implementation will need for us to keep a counter at all times to know which part we are working with. While in binary distributions, we can use boolean states easily to maintain this counter as it is intuitive.

Also, as others have explained in their answers, base of log doesn't change the theoretical big-O factor for time complexity.

Answer 4

You can and it sometimes implemented. However the worst case complexity of the algorithm will still be the same with regards to big-O notation.

Obviously divide and conquor algorithms are recursive by nature and so you will still split down until the problem is in a trivial state (a base case - eg sorting two numbers). You may arrive at this case sooner but do more work to get there, they will be the same in worst case performance.

Please see the following as this question has been asked before online and people have provided better and more complete answers than I could: https://softwareengineering.stackexchange.com/questions/197107/divide-and-conquer-algorithms-why-not-split-in-more-parts-than-two

Hope this helps!

Also from the above link which I found particulaly intesting:

"On the other hand, some tree-ish data structure do use a high branching factor (much bigger than 3, often 32 or more), though usually for other reasons. It improves utilization of the memory hierarchy: data structures stored in RAM make better use of the cache, data structures stored on disk require fewer reads HDD->RAM."