Without deeper thought, one might easily assume the time complexity of the tromino algorithm is O(n^4). This is because the algorithm divides the matrix into 4 smaller subproblems, suggesting a recursive solution that calls itself 4 times.

However, this is not the case. The actual time complexity of the algorithm is O(n^2). Let’s explore why.

What is the Tromino Tiling Problem (A Brief Overview)

A tromino is a block made of three squares in an L-shape.

The problem involves n x n grid (specifically, 2^n * 2^n grid) using these trominoes.

The Tiling must follow these conditions

• The entire grid must be covered by trominoes, except for one pre-selected missiing square.
• No trominoes can overlap.
• No tromino can extend the boundaries of the grid.

Strategy to solve the problem

We will use a divide-and-conquer approach, which is implemented using recursion.

1. Divide the n x n grid into four smaller n / 2 * n / 2 sub-grids or quadrants.
2. Place one tromino at the center of the grid, oriented so that it covers one square in each of the three quadrants that do not contain the missing square from the previous step.
3. This leaves for smaller sub-grids, each with exactly one square missing. These becomes four new, smaller versions of the original problem.
4. The recursion continues until the grid size is 2 x 2. This is the base case, which is solved by placing a single tromino to cover the three available squares.

Time Complexity

First, the work required to place a single tromino on the grid is constant, which we can denote as O(1).

In this algorithm, n represents the side length of the grid. In each recursive step, we do two things:

1. Perform the O(1) work of placing one tromino the center.
2. Launch four recursive calls for the for sub-grids, each with side length of n/2.

Therefore, the time complexity T(n) can be described by the recurrence relation:

T(n) = 4T(n/2) + O(1)

According to the Master Theorem, this recurrence solves to O(n^2).

So, why isn’t the time complexity O(n⁴)

The incorrect assumption of O(n^4) happens if you mix up variables.

Let’s define a new variable N, as the total number of squares, so N = n^2

If you try to write the recurrence using N, the side length n becomes √N. A subproblem with side length n/2 has a total of (n/2)^2 = N / 4 squares.

So in terms of N (total squares), the recurrence is T(N) = 4(T/4) + O(1).

By the Master Theorem, this solves to O(N). Since, N = n^2, the complexity is O(n^2).