divide-and-conquer.asc

Divide and Conquer

Divide and conquer is a strategy for solving algorithmic problems. It splits the input into manageable parts recursively and finally joins solved pieces to form the solution.

We have already implemented some algorithms using the divide and conquer technique.

Examples of divide and conquer algorithms:

• part04-algorithmic-toolbox.asc: divides the input into pairs, sort them, and them join all the pieces in ascending order.

• [quicksort-chap]: splits the data by a random number called "pivot," then move everything smaller than the pivot to the left and anything more significant to the right. Repeat the process on the left and right sides. Note: since this works in place doesn’t need a "join" part.

• Binary Search: find a value in a sorted collection by splitting the data in half until it sees the value.

• Permutations: Take out the first element from the input and solve permutation for the remainder of the data recursively, then join results and append the items that were taken out.

In general, the divide and conquer algorithms have the following pattern:

1. Divide data into subproblems.

2. Conquer each subproblem.

3. Combine results.

As you might know, there are multiple ways to solve a problem. Let’s solve the Fibonacci numbers using a divide and conquer algorithm. Later we are going to provide a more performant solution using dynamic programming.

Recursive Fibonacci Numbers

To illustrate how we can solve a problem using divide and conquer, let’s write a program to find the n-th Fibonacci number.

Fibonacci Numbers

Fibonacci sequence is a series of numbers that starts with 0, 1; the following values are calculated as the sum of the previous two. So, we have:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …​

We can get the n-th Fibonacci number with the following recursive program:

Recursive Fibonacci implemenation

link:../../../src/algorithms/fibonacci-recursive.js[role=include]

Let’s see how this fit divide and conquer:

• Divide: n is divided in two subproblems f(n-1) and f(n-2).

• Conquer: solve each subproblem independently

• Combine: sum the subproblem results to get the final solution.

The implementation above does the job, but what’s the runtime?

For that, let’s take a look at the job performed by calculating the fib(5) number. Since fib(5) = fib(4) + fib(3), we need to find the answer for fib(4) and fib(3). We do that recursively until we reach the base cases of fib(1) and fib(0). If we represent the calls in a tree, we would have the following:

graph G {
    "fib(5)" -- { "fib(4)", "fib(3)" }
    "fib(4)" -- { "fib(3)*", "fib(2)" }
    "fib(3)" -- { "fib(2)*", "fib(1)" }
    "fib(2)" -- { "fib(1)*", "fib(0)" }
    "fib(2)*" -- { "fib(1)***", "fib(0)*" }
    "fib(3)*" -- { "fib(2)**", "fib(1)**" }
    "fib(2)**" -- { "fib(1)****", "fib(0)**" }

    // red colors
    "fib(0)*" [color="#FF5252" label="fib(0)"];
    "fib(0)**" [color="#FF5252" label="fib(0)"];
    "fib(1)*" [color="#FF5252" label="fib(1)"];
    "fib(1)**" [color="#FF5252" label="fib(1)"];
    "fib(1)***" [color="#FF5252" label="fib(1)"];
    "fib(1)****" [color="#FF5252" label="fib(1)"];
    "fib(2)*" [color="#FF5252" label="fib(2)"];
    "fib(2)**" [color="#FF5252" label="fib(2)"];
    "fib(3)*" [color="#FF5252" label="fib(3)"];
}

In the diagram, we see the two recursive calls needed to compute each number. So if we follow the O(branches^depth), we get O(2ⁿ). 🐢 NOTE: Fibonacci is not a perfect binary tree since some nodes only have one child instead of two. The exact runtime for recursive Fibonacci is O(1.6ⁿ) (still exponential time complexity).

Exponential time complexity is pretty bad. Can we do better?

You can notice every element in red, and with asterisks *, it’s called more than once in the call tree. We are repeating calculations too many times!

Those who cannot remember the past are condemned to repeat it.

— Dynamic Programming

For these cases, when subproblems repeat themselves, we can optimize them using dynamic programming. Let’s do that in the next section.