O(nlogn) Runningtime Approach

Question

the function consumes a list of int and produces the unique elements in the list in increasing order. For examples:

    singles([4,1,4,17,1]) => [1,4,17]

I only can do it in O(n^2) running time and wonder how to change into O(n) running time without loop.

      def singles(lst):
        if lst==[]: return []
        else:
        rest_fn = list (filter (lambda x: x!=lst[0], lst[1:]))
        return [lst[0]] + singles(rest_fn)

Python uses timsort which per wikipedia has worst case O(nlogn). I would expect set (which would be the easy way to map from a list of ints to a list of unique elements) to be O(N). (Also, just in case you are doing supercomputers, Python's implementation of timsort apparently fails if you have more than I think 2^48 elements (or something rather ridiculous for a standard exercise... apparently the Java implementation is rather a bit smaller) — Foon, Mar 17 '15 at 02:40
Better link that covers sort and set: https://wiki.python.org/moin/TimeComplexity (sorting a list is O(nlogn), creating set from a list is O(n) if I read between the lines correctly — Foon, Mar 17 '15 at 02:45
No, I mean that the built-in python function set() (which will take a list and convert it into a set, which is essentially a list of unique values) should be O(n) for at least average case. — Foon, Mar 17 '15 at 02:50
Another idea to make this faster: If you can back up further in the program, don't collect your items in a list. Instead, collect them in a set or ordered set which can then output the items in the presentation you want in O(1) time. — Dogweather, Mar 17 '15 at 21:48
@Dogweather good point (though I would think it would still be O(N) to output the whole set (O(1) to retrieve each element) unless I'm missing something), and also, I would think doing an ordered set (which isn't listed on either of the performance links I see) would require O(log N) to insert each element, making the creation be still O(N log N)... you're just making that be part of the initialization part which is a perfectly valid approach — Foon, Mar 17 '15 at 22:09
@Foon good question — it's been a while since i've looked into the complexity for inserts. Re. the output being O(1), afaik we usually measure "compares" (in sorting) to determine complexity. So if your ADT is already pre-sorted and pre-filtered, then no comparisons are necessary. Hence O(1). Of course, real-world needs may determine that even higher up-front cost is completely acceptable. E.g., items inserted in a parallel process, or only infrequently. — Dogweather, Mar 17 '15 at 22:21

score 2 · Answer 1 · edited May 23 '17 at 12:28

2

As discussed above, per https://wiki.python.org/moin/TimeComplexity (which is cited from Time complexity of python set operations? which also links to a more detailed list of operations, sorted should have time complexity O(nlogn). Set should have time complexity O(n). Therefore, doing sorted(set(input)) should have time complexity O(n) + O(nlogn) = O(nlogn)

Edit: If you can't use set, you should mention that, but as a hint, assuming you can use sorted, you can still do the pull out uniques in O(n) if you use a deque (which has O(1) worst case insertion). Something like

rez = deque()
last = None
for val in sorted(input):
   if val != last:
      rez.add(val) # or whatever deque uses to add to the end of the list
      last = val

edited May 23 '17 at 12:28

Community

1
1

answered Mar 17 '15 at 03:00

Foon

6,148
11
40
42

But if cannot use set in the fn? – Ye Yang Mar 17 '15 at 03:03
I am a little confused, can you help me to look at my approach and change to O(n)? – Ye Yang Mar 17 '15 at 21:33
It can't be changed to O(n). Only that _part_ of the answer can be O(n). – Dogweather Mar 17 '15 at 21:46
can you give me a approach to achieve O(n) without set and loop? @Dogweather – Ye Yang Mar 17 '15 at 21:58
Thanks @Dogweather. To be clear:by information theory reasons, fundamentally O(n log(n)) is the limit for comparison based sorting (see the wiki link in my comment above on TimSort). RadixSort (http://en.wikipedia.org/wiki/Radix_sort, see efficiency), can if you look at it right be considered O(n) but that depends on certain assumptions and I don't feel confident in trying to explain them and in practice, it's more O(k*n) where k ends up being awfully similar to log N. – Foon Mar 17 '15 at 22:04
What's the point of the deque? A list would do exactly the same thing with exactly the same time complexity. – user2357112 Mar 17 '15 at 22:13
what's the deque mean? – Ye Yang Mar 17 '15 at 22:15
deque is Double Ended Queue. Python provides this through collections. Per the performance links, inserting to a List is worst case O(N), which means that inserting (in theory) N items into a List is O(N^2), though any sane implementation is going to be amortized O(N). In practice, the worst case doesn't happen often (it would be most likely if the array backing list were sized at say 500 elements... for the first 500 elements, insertion is O(1); for the 501st, it may have to be O(N) as it has to allocate a bigger block and copy the existing 500 elements over to it. – Foon Mar 17 '15 at 22:23

O(nlogn) Runningtime Approach

1 Answers1