A new technique for computational complexity analysis

It is generally difficult to estimate tight lower bounds for many problems and algorithms. Traditionally, lower bounds are obtained either by reduction or by a direct analysis. In this paper, a new idea is presented for estimating the lower bounds of problems and algorithms. In conjunction with two algorithm design paradigms divide and conquer and incremental construction, we can derive good lower bounds from the lower bounds of the corresponding sub-problems.