Abstract
The longest increasing subsequence problem is as follows: Given a sequence of n real numbers, find a longest increasing subsequence of . There is a well-known O(n lg n)-time comparison tree algorithm for solving this problem. Also, a tight Ω(n lg n) lower bound in the comparison tree model is known. We prove a tight Ω(n lg n) lower bound in the more powerful algebraic decision tree model. The above lower bounds also apply to the apparently simpler problem of finding the length of a longest increasing subsequence.
Computing Reviews Category: