python - O(nlogn) Runningtime Approach -

the function consumes list of int , produces unique elements in list in increasing order. examples:

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

i can in o(n^2) running time , wonder how change 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) 

as discussed above, per https://wiki.python.org/moin/timecomplexity (which cited time complexity of python set operations? links 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 can't use set, should mention that, hint, assuming can use sorted, can still pull out uniques in o(n) if use deque (which has o(1) worst case insertion). like

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