Computing recurrence relations in O(log N) time

02 Feb 2013

A few days ago, while trying to solve a problem which went as;

You have unlimited supply of colored rectangles. There are five types of them:

  • Red 1x3 rectangle
  • Green 2x2 rectangle
  • Blue 3x1 rectangle
  • Yellow 3x3 rectangle

You want to build as many different 3xN rectangles as possible. Note that you are not allowed to rotate the rectangles. ()

The first step to find a recurrence relation for the problem, that was the relatively easy part and i’m not going to go into much detail here. The recurrence relation i’ve come up with for the number of different 3xN rectangles was

With the initial values

So I went on and implemented the most straightforward (alright, not the most straightforward solution per se, but relatively straightforward) solution, using the simple dynamic programming method of computing recurrence relations in complexity. However, this solution simply blew up in my face when used with values larger than or so.

So, we need to find an order of magnitude more efficient solution. Turns out there is such a solution, which lies buried deep within the secrets of matrices. The initial step to the solution is the following definition;

Using that and the definition of matrix multiplication; we can write the following equation:

If we name the 3x3 matrix , the general formula for the equation becomes . However, and are not defined, so just transform the equation into

So, what does this form give us? For that, we’ll need to look into Exponentiation by Squaring. It’s a algorithm for finding . It can be described in pseudocode as;

def exp(base,n):
    if(n==0): 1
    elsif(even?(n)): exp(base*base, n/2)
    else: exp(base*base, (n-1)/2)*base

This algorithm is designed for exponentiating integers, but it happens to work in our case as well1, just replace the 1 with identity matrix and the multiplication operator with matrix multiplication.

So; the steps of solution to the problem were

  1. Find a recurrence relation that gives the answer to the question
  2. Transform it to a matrix multiplication
  3. Code the matrix multiplication and fast exponentiation functions (relatively easy)
  4. Use those functions to compute the recurrence relation for the very large number , in time.

Note that this method also works for non-homogeneous recurrence relations. For example; given the recurrence relation , we can define


such that and use exponentiation by squaring.

  1. Why this works is another question, the exponentiation by squaring algorithm can be defined on Rings and both integers and square matrices constitute rings. (The main difference between them is; integers form a commutative ring while square matrices do not.)