Master Theorem
Determine the asymptotic bound of recursive algorithms via standard recurrences
The Sierpinski triangle is a confined recursion of triangles that form a fractal
Base Case
Recursive Case
Parameters
Asymptotic Bound
Big-O Comparisons
Pragmatic Analysis
Example 1: Karatsuba Multiplication
C++
Type go( Type x, Type y )
{
if( x < 10 || y < 10 ) return x * y;
auto i{ log(x) }, j{ log(y) }, N{ min(i,j) }, p{ pow(N/2) }, // (p)ivot
a{ x / p }, b{ x % p },
c{ y / p }, d{ y % p },
u{ go(a,c) }, v{ go(a+b,c+d) }, w{ go(b,d) };
return( u * pow( N ) + ( v -u -w ) * pow( N/2 ) + w );
}
Python
def go( x, y ):
if x < 10 or y < 10:
return x * y
i = log10( x ) # number of digits in x
j = log10( y ) # number of digits in y
N = min( i, j ) # minimum number of digits between x, y
p = pow10( N/2 ) # pivot position
a = x / p # a is the first half of x
b = x % p # b is the second half of x
c = y / p # c is the first half of y
d = y % p # d is the second half of y
u = go( a, c )
v = go( a+b, c+d )
w = go( b, d )
return u * pow10( N ) + ( v -u -w ) * pow10( N/2 ) + w
The rate of sub-problem proliferation a = 3
since go()
recursively invokes itself three times. The rate of work shrinkage per sub-problem b = 2
since each sub-problem computes upon half the input. The work performed outside recursive calls is O( n )
since each input digit is read once to determine the number’s length, thus d = 1
.
Therefore:
Example 2: Merge Sort
C++
Collection go( Collection&& A )
{
if( A.size() < 2 )
return A;
auto pivot = A.begin() + A.size() / 2;
return merge( go({ A.begin(), pivot }), go({ pivot, A.end() }) );
}
Collection merge( Collection&& lhs, Collection&& rhs, Collection res={} ) // merge (res)ult
{
auto L = lhs.begin(), R = rhs.begin();
while( L != lhs.end() && R != rhs.end() )
res.push_back( ( *L < *R )? *L++ : *R++ );
res.insert( res.end(), L, lhs.end() ), res.insert( res.end(), R, rhs.end() ); // append left-overs ( if applicable )
return res;
}
Python
def go( A ):
if len( A ) < 2:
return A
P = len( A ) // 2
return merge( go( A[ :P ] ), go( A[ P: ] ) )
def merge( L, R ):
A = []
i = 0
j = 0
while i < len( L ) and j < len( R ):
if L[ i ] < R[ j ]:
A.append( L[ i ] )
i += 1
else:
A.append( R[ j ] )
j += 1
A.extend( L[ i: ] )
A.extend( R[ j: ] )
return A
The rate of sub-problem proliferation a = 2
since go()
recursively invokes itself two times. The rate of work shrinkage per sub-problem b = 2
since each sub-problem computes upon half the input. The work performed outside recursive calls is O( n )
since each input array is read once to determine the merge result, thus d = 1
.
Therefore:
Citations
- Images: wikipedia.org
- Mathematical formulas: codecogs.com