Given a set S of nonoverlapping axis-parallel rectangles placed inside a rectangular region B, a partition of the space B\S is called a ‘free space partition’. A simple proof of a formula on the number of rectangles in a minimum free space partition is presented. Based on this formula, it is shown that a minimum free space partition can be computed using a well known geometric graph search algorithm in O(n3/2 log n) time.