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