CODEWITHSUNDEEP
algorithmhashset
mjnichol
mjnichol

Reputation: 361

Space complexity of algorithm to copy a list into a HashSet

What is the space complexity for an algorithm which places each element from a list into a HashSet? Is it O(n), where n is the size of the list or is it O(k), where k is the number of unique elements in the list. Since the HashSet only grows when we add unique elements to it it seems to me that the latter is correct.

Upvotes: 0

Views: 4606

Answers (1)

aa333
aa333

Reputation: 2576

Space complexity of any algorithm takes into account the size of the input. It is a measure of the maximum working memory that will be needed during the execution of the algorithm. So for O(n) size input the space complexity has to be at least O(n). Source

So given the algorithm used O(n) just for the input, and it isn't a really bad implementation i.e. it uses constant amount of space as it iterates over the list and we know that k < n, so input size will always be the dominating factor in space complexity. So overall the space complexity will be O(n).

Upvotes: 1

Related Questions