title: An  ×  chessboard is to be cut into its · unit squares
body: <p>An  ×  chessboard is to be cut into its · unit squares. At each step, you can make either one horizontal cut or one vertical cut. The first cut will split the board into two sub-boards; after that each cut splits one remaining sub-board into two. The cost of a cut equals the number of unit squares remaining in the smaller of the two resulting sub-boards. For example, a horizontal cut on a 2 × 3 board results in two 1 × 3 sub-boards and costs 3, whereas a vertical cut results in sub-boards of dimensions 2 × 1 and 2 × 2 and costs 2. Costs are additive: the cost of a sequence of cuts equals the sum of their individual costs. Describe an algorithm to compute the minimum total cost of reducing the  ×  board into its unit squares. Prove its correctness and show your analysis of its time complexity.</p>
  
  <p>My solution goes as follows:
  1. I follow the greedy approach of checking for the highest between m (row) and n (column) and making a cut. 
  2. If m is higher I make a vertical cut and other a horizontal cut.
  3. This gives me the lowest cut cost in every step.
  4. I follow divide and conquer and recursively follow the approach until I have m x n = 1 x 1</p>
  
  <p>This seems to be working but what I am struggling with is to derive the time complexity and proving the correctness of my algorithm.</p>
  
  <p>My expression of time complexity is T(m<em>n) = 2 T(m</em>n/2) + theta(n). </p>
  
  <p>Can someone advice me how I can do this?</p>