Explanation and time/space complexity of tri tiling

Question

I am having problems understanding what exactly is going on in the solve function below. I see what it does, however it still is unclear to me - I cannot visualize it, or just get myself to understand it. Can someone explain it?

Original problem statement (link):

In how many ways can you tile a 3xn rectangle with 2x1 dominoes?

Here is a sample tiling of a 3x12 rectangle.

Code (taken from here):

#include <stdio.h>
int dp[32];
int solve(int n)
{
    if(dp[n]!=-1)
        return dp[n];
    else
    {
        int i;
        int res = 3*solve(n-2);
        for(i=4;i<=n;i+=2)
            res+=2*solve(n-i);
        return dp[n]=res;
    }
}
int main()
{
    int i;
    for(i=0;i<32;i+=2)
        dp[i]=-1;
    for(i=1;i<32;i+=2)
        dp[i]=0;
    dp[0]=1;
    scanf("%d",&i);
    while(i!=-1)
    {
        printf("%d\n",solve(i));
        scanf("%d",&i);
    }
    return 0;
}

Another thing is, what could be the time and space complexity of this algorithm? Since it is a recursive function, it might be O(log N), but I am not sure about that either.

Answer 1

Technically speaking, the runtime is O(1) because there is an upper bound on the size of the input (specifically, 32). But let's assume for a minute that the problem size isn't at most 32 and think about that problem. In that case, the runtime is O(n²). After a recursive call of some size has been made, any future recursive calls of the same size run in time O(1). This is due to the use of memoization in the dp table. This means that we can compute the total runtime by summing up, across all possible recursive calls that could be made, the amount of time required to fill in the dp table.

On a call of size n, there is O(n) work done to fill in the array. You can see this by the for loop that starts at 4 and counts up to n by two's, at each point doing O(1) work. Since the recursive calls are on sizes 0, 1, 2, ..., n, we have O(n) calls doing O(n) work each for a total of O(n²) total work.

Hope this helps!