☕ Tech Dive - Divide and Conquer Algorithms

Hey Guys,

Today’s tech dive is going to be on Divide and Conquer algorithms.

We’ll be talking about

• What are Divide and Conquer Algorithms?

• Examples of Divide and Conquer

• Calculating the Time Complexity of Divide and Conquer Algorithms

What is Divide and Conquer?

The divide and conquer paradigm breaks your problem down into more sub-problems of the same type, until these become simple enough to be solved directly (the base case). This is the divide step.

Then, it combines the solutions to the subproblems in some form to get the solution to the original problem. This is the combine step.

You can also perform optimizations in the divide or combine steps, resulting in paradigms like Dynamic Programming (storing the answers to subproblems in cache).

Mergesort is a classic sorting algorithm that uses Divide and Conquer to sort a list of numbers.

The red boxes are part of the divide steps. The green boxes are part of the combine steps.

The essence of the implementation of MergeSort is

Now, one issue that comes up is how can you analyze the time complexity of this algorithm?

With divide and conquer algorithms, we’re typically calling the function recursively.

In our MergeSort example, we’re calling the mergeSort function recursively on firstHalf and secondHalf (lines 9 and 10).

We’ll need the time complexity of those two lines to figure out the time complexity of the entire function. This creates a catch-22 of sorts.

Time Complexity of Divide and Conquer Algorithms

The way we can resolve this is through the Master Method.

The Master Method requires us to express our algorithm as a recurrence. A recurrence is an equation that expresses the output as a function of the equation itself.

So, an example is the factorial operation.

n! = 1 * 2 * 3 * ... * ( n - 1) * n

You can express a factorial as a recurrence. The recurrence would be

F(n) = n * F(n - 1)

with 0! = 1 as the base case.

Going back to our MergeSort example…

Let’s express the time complexity as a recurrence.

The base case (lines 3 - 4) will take constant time, O(1).

Both lines of the divide step (lines 6 - 7) will take linear time. That’s because we’re copying over the first half of nums to firstHalf and copying the second half of nums to secondHalf. Therefore both of those steps are O(n).

Now, we have to solve our subproblems (lines 9 - 10). The inputs to both of these subproblems will be half the list, so it can be expressed as M(n / 2) where M(n) is the time complexity of MergeSort. Since we’re calling mergeSort twice, the entire solving subproblem step will take 2 * M(n / 2).

After that, we have the combine step (line 12). This calls a merge function. The function just iterates through firstHalfSorted and secondHalfSorted and combines the two lists into a final, sorted list. It takes linear time, so another O(n) operation.

The return statement at the end takes constant time.

We can put this together to come up with our recurrence.

M(n) = 2 * M( n / 2) + O(n)

Now, how do we turn this recurrence into a time complexity in Big O notation?

We can use The Master Method.

The Master Method is a simple formula that you can plug your recurrence into, and it’ll output a time complexity.

However, your recurrence must be in standard form in order to use the Master Method.

A recurrence in standard form is a recurrence that looks like

T(n) = a * T(n / b) + O(n^d)

Where a, b and d can represent any constant.

The vast majority of the recurrences you’ll come across in coding interviews can be expressed in standard form.

The Master Method formula is….

So, going back to our MergeSort recurrence of

M(n) = 2 * M( n / 2) + O(n)

a = 2, b = 2 and d = 1.

Therefore, 2 = 2^1, which means we’re in Case 1.

Therefore, our time complexity is O(n log n). That’s it!

You should definitely memorize all 3 cases of The Master Method for your coding interviews.

If you’d like some intuition for why The Master Method works, check out this video.

Here’s the code for Binary Search.

Reply back to this email with the recurrence and the time complexity of this function so you can test your understanding!