CODEWITHSUNDEEP
javascriptbig-ospace-complexity
lightspeed
lightspeed

Reputation: 313

Space complexity of variable that grows and shrinks within function

I am working on a problem in which I need to find the one value in an array that doesn't have duplicates. To solve the problem, I'm adding each value to a hashTable the first time it occurs and removing it with its second occurrence.

In the end, the hashTable will only contain the character that had a single occurrence in the array. What would be the space complexity for a problem like this where the hashTable grows but then also shrinks?

I expect that the space complexity is O(1) since irrespective of the input size, the final size of the hashTable will be of length 1.

*Of note: Assume that the input array of duplicates will only have 1 item that has a single occurrence and you don't need to worry about any other edge cases.

Upvotes: 0

Views: 109

Answers (2)

Michael Pratt
Michael Pratt

Reputation: 3496

Space complexity is not just a measure of the space your algorithm uses at the end of the algorithm given ideal circumstances. It's generally a measure of how much your algorithm takes to solve. In your case, since it has to loop through and potentially remember the entire input array once (assuming a proper hashtable implementation with O(1) read/write access), it is O(n) - Even with assuming there are only pairs of duplicates and one single value. Order notation generally doesn't take into account something like O(n/2).

As Nuno mentioned, your algorithm will not work if you need to take in to account triplicates. Even if a particular question stated they can't happen now, it's important to remember for the future - I use a variation of this class of problem as an interview question, and people frequently forget triplicates.

Those candidates don't pass.

Upvotes: 0

Nuno Sousa
Nuno Sousa

Reputation: 882

What if there is an odd number of duplicates? The hashtable loses the value then gains it again!

The proper way (I think) O(n) WCS is to use a table (not necessarily an hash table, if you don't hash anything). After that remove all values greater than 1 and voilá.(still O(n)).

Edit: Explanation of complexity: In terms of space, the worst case scenario is that each value occurs once in the initial array, meaning that the resulting table has 1 entry for each member of the initial array. Meaning N entries. This algorithm is computationaly linear.

If you were really trying to get to the bottom of this in terms of complexity, you would need to acess the computational requirements of your "hashtable" - actually use an hash? can I preallocate the entire Counter-Domain as an array of integers? These are actually more dependent on the actual application of this algorithm. In any case it's mostly a P class super fast algorithm.

Upvotes: 1

Related Questions