Algorithms included: Master Theorem, Merge Sort, Strassen's Matrix Multiplication, Median of Medians, Fast Fourier Transform
There are mainly three ways for solving recurrences. One of them is Master Method. Master Method is
a direct way to get the solution. The master method works only for following type of recurrences or
for recurrences that can be transformed to type:
T(n) = aT(n/b) + f(n) where a >= 1 and b > 1
where,
n = size of input
a = number of subproblems in the recursion
n/b = size of each subproblem. All subproblems are assumed to have the same size.
f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions
There are following three cases:
Example:
Merge Sort is one of the most popular sorting algorithms that is based on the principle of Divide and Conquer Algorithm. Using the Divide and Conquer technique, we divide a problem into subproblems. When the solution to each subproblem is ready, we combine the results from the subproblems to solve the main problem. The merge sort algorithm recursively divides the array into halves until we reach the base case of array with 1 element. After that, the merge function picks up the sorted sub-arrays and merges them to gradually sort the entire array.
Algorithm goes as follows:
def mergeSort(array):
if len(array) > 1:
# r is the point where the array is divided into two subarrays
r = len(array)//2
L = array[:r]
M = array[r:]
# Sort the two halves
mergeSort(L)
mergeSort(M)
i = j = k = 0
# Until we reach either end of either L or M, pick larger among
# elements L and M and place them in the correct position at A[p..r]
while i < len(L) and j < len(M):
if L[i] < M[j]:
array[k] = L[i]
i += 1
else:
array[k] = M[j]
j += 1
k += 1
# When we run out of elements in either L or M,
# pick up the remaining elements and put in A[p..r]
while i < len(L):
array[k] = L[i]
i += 1
k += 1
while j < len(M):
array[k] = M[j]
j += 1
k += 1
Average Case: O(n log n)
Worst Case: O(n log n)
Best Case: O(n log n)
Space Complexity: O(n)
Stable: Yes
In-place: Yes
Auxiliary Space: O(1)
Time Complexity: O(n log n)
Strassen’s Matrix multiplication can be performed only on square matrices where n is a power of 2. Order of both of the matrices are n × n. This happens by decreasing the total number if multiplication performed at the expenses of a slight increase in the number of addition. Strassen algorithm is a recursive method for matrix multiplication where we divide the matrix into 4 sub-matrices of dimensions n/2 x n/2 in each recursive step. Better way of explanation of this is given here.
In Strassen’s matrix multiplication there are seven multiplication and four addition, subtraction in total. They are:
import numpy as np
def split(matrix):
"""
Splits a given matrix into quarters.
Input: nxn matrix
Output: tuple containing 4 n/2 x n/2 matrices corresponding to a, b, c, d
"""
row, col = matrix.shape
row2, col2 = row//2, col//2
return matrix[:row2, :col2], matrix[:row2, col2:], matrix[row2:, :col2], matrix[row2:, col2:]
def strassen(x, y):
"""
Computes matrix product by divide and conquer approach, recursively.
Input: nxn matrices x and y
Output: nxn matrix, product of x and y
"""
# Base case when size of matrices is 1x1
if len(x) == 1:
return x * y
# Splitting the matrices into quadrants. This will be done recursively
# until the base case is reached.
a, b, c, d = split(x)
e, f, g, h = split(y)
# Computing the 7 products, recursively (p1, p2...p7)
p1 = strassen(a, f - h)
p2 = strassen(a + b, h)
p3 = strassen(c + d, e)
p4 = strassen(d, g - e)
p5 = strassen(a + d, e + h)
p6 = strassen(b - d, g + h)
p7 = strassen(a - c, e + f)
# Computing the values of the 4 quadrants of the final matrix c
c11 = p5 + p4 - p2 + p6
c12 = p1 + p2
c21 = p3 + p4
c22 = p1 + p5 - p3 - p7
# Combining the 4 quadrants into a single matrix by stacking horizontally and vertically.
c = np.vstack((np.hstack((c11, c12)), np.hstack((c21, c22))))
return c
Time complexity of Strassen’s matrix multiplication is O(n^2.807).
The median-of-medians algorithm is a deterministic linear-time selection algorithm. The algorithm works by dividing a list into sublists and then determines the approximate median in each of the sublists. Then, it takes those medians and puts them into a list and finds the median of that list. It uses that median value as a pivot and compares other elements of the list against the pivot. If an element is less than the pivot value, the element is placed to the left of the pivot, and if the element has a value greater than the pivot, it is placed to the right. The algorithm recurses on the list, honing in on the value it is looking for.
The algorithm takes in a list and an index which is median-of-medians(A, i). Assume that all elements of A are distinct (though the algorithm can be further generalized to allow for duplicate elements).
def median_of_medians(A, i):
#divide A into sublists of len 5
sublists = [A[j:j+5] for j in range(0, len(A), 5)]
medians = [sorted(sublist)[len(sublist)/2] for sublist in sublists]
if len(medians) <= 5:
pivot = sorted(medians)[len(medians)/2]
else:
#the pivot is the median of the medians
pivot = median_of_medians(medians, len(medians)/2)
#partitioning step
low = [j for j in A if j < pivot]
high = [j for j in A if j > pivot]
k = len(low)
if i < k:
return median_of_medians(low,i)
elif i > k:
return median_of_medians(high,i-k-1)
else: #pivot = k
return pivot
The master theorem is used to derive its complexity which comes to O(n).
The Fast Fourier Transform is used for polynomial multiplication. The time to multiply two polynomials of degree-bound n in point-value form is Θ(n).The inverse of evaluation determining the coefficient form of a polynomial from a point-value representation is called interpolation.
Overview of the FFT Algorithm is as follows:
Let m = 2n-1. [so degree of C is less than m]
Pseudocode of the algorithm is as follows:
Recursive_FFT(a){
n = length(a) // a is the input coefficient vector
if n = 1
then return a
// wn is principle complex nth root of unity.
wn = e^(2*pi*i/n)
w = 1
// even indexed coefficients
A0 = (a0, a2, ..., an-2 )
// odd indexed coefficients
A1 = (a1, a3, ..., an-1 )
y0 = Recursive_FFT(A0) // local array
y1 = Recursive-FFT(A1) // local array
for k = 0 to n/2 - 1
// y array stores values of the DFT
// of given polynomial.
do y[k] = y0[k] + w*y1[k]
y[k+(n/2)] = y0[k] - w*y1[k]
w = w*wn
return y
}
Complexity of the FFT is O (n log n). If n is in fact a power of 2 , then the complexity is O (n log 2n) , where log 2n is the number of times n can be factored into two integers.