Divide and Conquer

 

Divide and Conquer

At this point, we can begin to establish whether the runtime of an algorithm is O(n) or O(n²) etc. but we still need to think about cases where it is less obvious how many times a loop will repeat itself.

Divide and conquer algorithms are a design paradigm for solving problems by dividing the problem into smaller subproblems, solving the subproblems recursively, and then combining the solutions to the subproblems to solve the original problem.

Here is a general outline of the divide-and-conquer approach:

1.       Divide: Divide the problem into smaller subproblems.

2.       Conquer: Recursively solve the smaller subproblems.

3.       Combine: Combine the solutions to the subproblems to solve the original problem.

One of the key advantages of divide-and-conquer algorithms is that they can often be more efficient than other algorithms, due to their recursive nature. Many problems can be divided into subproblems that are similar to the original problem, and this allows us to reuse solutions and avoid recalculating them.

Examples of divide and conquer algorithms include merge sort, quick sort, and the Karatsuba algorithm for multiplying large integers.

There are some trade-offs to consider when using divide-and-conquer algorithms. One disadvantage is that they may have a larger constant factor than other algorithms, due to the overhead of dividing and combining the subproblems. Additionally, divide-and-conquer algorithms are not always the best choice for problems with small input sizes, as the overhead of dividing and combining the subproblems may outweigh the benefits.

Overall, divide and conquer algorithms are a powerful tool for solving problems and can be very efficient for large inputs.

The classic case is the runtime of ‘divide and conquer’ algorithms. You should have come across the notion of binary search before - but take some time to think about how long it takes to find a name in a telephone directory or a word in a dictionary. You don’t have to check every single item in the book. You can focus in on the data you want very quickly. Why is this?

The time it takes to find a name in a telephone directory or a word in a dictionary is much faster than searching through the entire book because both books are organized in a way that allows us to focus in on the data we want very quickly.

Telephone directories and dictionaries are typically organized in alphabetical order, which allows us to use a binary search algorithm to find a specific name or word. Binary search is a divide-and-conquer algorithm that has a time complexity of O(log n), where n is the number of items in the book. This means that the running time of the algorithm increases very slowly as the size of the input grows, making it much faster than a linear search algorithm, which has a time complexity of O(n).

In a binary search, we start by looking at the middle item in the book. If the item we are looking for comes before the middle item, we can eliminate the second half of the book from our search. If the item we are looking for comes after the middle item, we can eliminate the first half of the book from our search. We then repeat this process on the remaining half of the book until we find the item we are looking for, or until we determine that the item is not in the book.

Because binary search allows us to eliminate half of the items from our search at each step, it can find a specific name or word in a telephone directory or dictionary much faster than a linear search.