0

okay,so i was searching around the web and trying out for my self and yet i could'nt get the answer

what is the lower bound for counting the number of unique integers in a linked list(a list in particular and not an array)

it seems like the lower bound is O(nLogN) time complexity and O(1) space complexity.

or O(n) times complexity and O(n) space complexity.

is there an O(n) times complexity with O(1) space complexity?? and would your answer change upon switching it from a list to an array?

-- just to be clear,here's an example: {1,4,2,20,2,1,1} the number of unique items is 2 - {4,20}

naor.z
  • 107
  • 8
  • http://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an-array/1533667#1533667 – Dmitry Bychenko Feb 21 '17 at 11:45
  • When you think that list|array is such a big deal then better be clear about what kind of list. – H H Feb 21 '17 at 11:55
  • i've seen his answer,though he writes "It's guaranteed to be O(1) in axillary space (the recursion is a tail call), and is typically O(N) time complexity." , i want to know if exists a worst case O(N),not just typically – naor.z Feb 21 '17 at 11:56
  • How do you remove dupes in a linked list in O(n log n) time and O(1) space? It seems impossible to me. – Paul Hankin Feb 21 '17 at 13:47
  • 2
    inplace marge sort(no auxillaries are needed in a linked list),and then just traversing the list removing dupes – naor.z Feb 21 '17 at 14:19
  • 1
    Doesn't merge sort require O(log n) space for the call stack? – Paul Hankin Feb 21 '17 at 17:48
  • technically you are correct,but i ignored the space used by the recursion call for that matter. – naor.z Feb 23 '17 at 09:58

0 Answers0