Tight Ω(n lg n) lower bound for finding a longest increasing subsequence

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.

Keywords:

• Longest increasing subsequence
• decision tree model
• lower bound

Computing Reviews Category:

• F2.2