Complexity of trominoes algorithm

Question

What is or what should be complexity of (divide and conquer) trominoes algorithm and why?

I've been given a 2^k * 2^k sized board, and one of the tiles is randomly removed making it a deficient board. The task is to fill the with "trominos" which are an L-shaped figure made of 3 tiles.

Tiling Problem

– Input: A n by n square board, with one of the 1 by 1 square missing, where n = 2k for some k ≥ 1.

– Output: A tiling of the board using a tromino, a three square tile obtained by deleting the upper right 1 by 1 corner from a 2 by 2 square.

– You are allowed to rotate the tromino, for tiling the board. Base Case: A 2 by 2 square can be tiled.

Induction:

– Divide the square into 4, n/2 by n/2 squares.

– Place the tromino at the “center”, where the tromino does not overlap the n/2 by n/2 square which was earlier missing out 1 by 1 square.

– Solve each of the four n/2 by n/2 boards inductively.

Answer 1

This algorithm runs in time O(n²) = O(4^k). To see why, notice that your algorithm does O(1) work per grid, then makes four subcalls to grids whose width and height of half the original size. If we use n as a parameter denoting the width or height of the grid, we have the following recurrence relation:

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

By the Master Theorem, this solves to O(n²). Since n = 2^k, we see that n² = 4^k, so this is also O(4^k) if you want to use k as your parameter.

We could also let N denote the total number of squares on the board (so N = n²), in which case the subcalls are to four grids of size N / 4 each. This gives the recurrence

S(N) = 4S(N / 4) + O(1)

This solves to O(N) = O(n²), confirming the above result.

Hope this helps!