What are some examples of divide and conquer algorithms?

1 Merge sort

Merge sort is a sorting algorithm that divides the input array into two halves, recursively sorts each half, and merges the two sorted halves into one sorted array. The merging process involves comparing the elements from each half and placing the smaller one into the output array until both halves are exhausted. Merge sort has a time complexity of O(n log n) for the average and worst cases, where n is the number of elements in the array. Merge sort is stable, meaning that it preserves the relative order of equal elements, and can be easily adapted to sort linked lists, files, and streams.

2 Quick sort

Quick sort is another sorting algorithm that divides the input array into two partitions, one with elements smaller than a pivot element and one with elements larger than or equal to the pivot element. The pivot element can be chosen randomly, or by using some heuristic, such as the median of three. Quick sort then recursively sorts each partition until the array is sorted. Quick sort has a time complexity of O(n log n) for the average case, but O(n^2) for the worst case, where n is the number of elements in the array. Quick sort is not stable, meaning that it may change the relative order of equal elements, and requires extra space for the recursive calls.

3 Binary search

Binary search is a searching algorithm that finds the position of a target element in a sorted array by repeatedly comparing it with the middle element and narrowing down the search range. Binary search starts with the whole array as the search range, and then halves it by comparing the target element with the middle element. If the target element is equal to the middle element, the search is over. If the target element is smaller than the middle element, the search continues in the left half of the range. If the target element is larger than the middle element, the search continues in the right half of the range. Binary search has a time complexity of O(log n) for the average and worst cases, where n is the number of elements in the array. Binary search is efficient, but requires the array to be sorted in advance.

4 Strassen's algorithm

Strassen's algorithm is a matrix multiplication algorithm that reduces the number of scalar multiplications needed to multiply two n x n matrices by dividing them into four n/2 x n/2 submatrices, computing seven intermediate matrices using recursive calls, and combining them to obtain the final result. Strassen's algorithm has a time complexity of O(n^2.807) for the average and worst cases, where n is the dimension of the matrices. Strassen's algorithm is faster than the naive algorithm, which has a time complexity of O(n^3), but requires more space and may introduce numerical errors due to rounding.

5 Convex hull

Convex hull is a computational geometry problem that finds the smallest convex polygon that contains a given set of points in the plane. A convex polygon is one that has no interior angles greater than 180 degrees, and a point is contained in a polygon if it lies on the boundary or in the interior of the polygon. Convex hull can be solved by using a divide and conquer algorithm that splits the points into two subsets by a vertical line, recursively computes the convex hulls of each subset, and merges them by finding the upper and lower tangents that connect the two hulls. The time complexity of this algorithm is O(n log n) for the average and worst cases, where n is the number of points. Convex hull has many applications, such as collision detection, clustering, and image processing.