title: Complexity of trominoes algorithm
body: <p>What is or what should be complexity of (divide and conquer) trominoes algorithm and why?</p>
  
  <p>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.</p>
  
  <p>Tiling Problem</p>
  
  <p>– Input: A n by n square board, with one of the 1 by 1 square
  missing, where n = 2k for some k ≥ 1.</p>
  
  <p>– 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.</p>
  
  <p>– You are allowed to rotate the tromino, for tiling the board.
  Base Case: A 2 by 2 square can be tiled.</p>
  
  <p>Induction:</p>
  
  <p>– Divide the square into 4, n/2 by n/2 squares.</p>
  
  <p>– 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.</p>
  
  <p>– Solve each of the four n/2 by n/2 boards inductively.</p>