TJ Gaffney - 8 months ago 40

Python Question

I'm studying this algorithm for the first time. CLRS (15-4.6) asks to write an algorithm to run in O(n lg n) time. The algorithm I came up with seems to run in O(n). I think I must be misunderstanding something, because even wikipedia says it should take O(n lg n) time. (https://en.wikipedia.org/wiki/Longest_increasing_subsequence)

Could somebody tell me why this algorithm (in Python) doesn't work in general or isn't O(n) or doesn't answer the question??

`"""Attempts to find maximal ordered subsequence in linear time."""`

def subseq(n):

"""Assumes the elements of n are unique"""

if len(n) == 1:

return n[:]

first = [n[0]]

second = []

for i in range(1,len(n)):

if n[i] > first[-1]:

second = first[:]

first.append(n[i])

elif not second or n[i] > second[-1]:

first = second[:]

first.append(n[i])

return first

print subseq([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])

Answer

I'll leave some of the debugging to you, but the following does not produce the maximum length substring using your algorithm. I simply added a few numbers to the example you had, so it should have produced `[0, 4, 6, 9, 11, 15]`

again, but didn't:

```
>>> print(subseq([0, 12,12,15,14 ,8, 4, 12, 14, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]))
[0, 12, 13, 15]
```

Source (Stackoverflow)