Can someone explain me why the following algorithm for LIS is not O(n)?

Question

The following code traverses the list once and finds the LIS. I don't see why the DP algorithm should take O(n2).

//C
int lis(int *a, int l){
  if(l == 0) return 1;
  else if(a[l] > a[l - 1])  return  1 + lis(a, l - 1);
  else  return lis(a, l - 1);
}

int main(){
  int a[] =  { 10, 22, 9, 33, 21, 50, 41, 60 };
  cout << lis(a, sizeof(a)/sizeof(a[0]) - 1);
}

% erlang
lis([_H]) -> 1;
lis([H1, H2 |T]) when H1 > H2 ->  1 + lis([H2|T]);
lis([_H|T]) -> lis(T).

main() ->  lis(lists:reverse([ 10, 22, 9, 33, 21, 50, 41, 60 ])).

Answer 1

Your current implementation of lis/1 function is O(n), I don't see any reasons to doubt. But there is some problem. You implementation doesn't actually calculate valid LIS. Try

lis(lists:reverse([1,2,3,4,1,2]))

for error example. Longest increasing sequense is [1,2,3,4], right? But your algorith returns 6 as result.

• First error in your algorithm in that you increase result each time, when you encountered element that greater than previous. But you should increase result only if current element is greater that greatest element of your current LIS. So (according example above) you should remember 4 and not increase result after you detected then 2 is greater than 1.

• But this not only thing you have to do. Consider sequence 1 2 3 6 4 5. For 5 first elements LIS has length of 4. But there is TWO possible options there - either 1 2 3 4 or 1 2 3 6. Which you should take as actual LIS?

• And so on, and so on...

Another example comes directly from wiki page.

Sequence [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] has LIS [0, 2, 6, 9, 13, 15] (e.g., 6 elements), but your algorythm says 9.

And, (correct me, if I'm wrong), LIS implementation must return subsequence itself, but not only its length.

Answer 2

Good news: the above implementation is not quadratic.

Bad news: the above function does not calculate the longest subsequence of increasing elements (defined as the LIS).

To respond to your question, the actual LIS problem has quadratic complexity, not the DP algorithm itself, which is merely a step towards the final solution. In fact, the DP algorithm is repeated for all elements of the list (you need to calculate all the DP[i]), which is why the complete algorithm is categorized as O(n^2).