Set creation takes O(N) space and O(N log(N)) time, and the inner loop condition (if not x in b) is also log(N). So it's slower in time and it requires more space. People usually don't distinguish between O(N) and O(2N), because actual performance is dependent on implementation choices and CPU cache locality and all that stuff isn't really part of algorithmic complexity analysis.
I do like your solution better though, but mostly because it doesn't mutate the array passed to the function. A function called "firstMissingPositive" shouldn't modify state.
Why would set creation (and the not x in b inner loop) take O(Nlog(N)) time? I would have thought it would have just required a hash-lookup for each element (O(1)?) being added (and then, a decision to either add the element or not.
Actual times definitely more than O(N) growth.
a10k = []
for x in range(10000):
a10k.append(randint(1,20000))
%timeit b10k = set(a10k)
10k elements = 364 microseconds/loop
100k elements = 5 milliseconds/loop
1mm elements = 170 milliseconds/loop
10mm elements = 2.4 seconds/loop.
100mm elements = 34.5 seconds/loop
Presumably the jump from 100k elements to 1mm elements hit that "cache locality" boundary you were referring to.
Comments
Set creation takes O(N) space and O(N log(N)) time, and the inner loop condition (if not x in b) is also log(N). So it's slower in time and it requires more space. People usually don't distinguish between O(N) and O(2N), because actual performance is dependent on implementation choices and CPU cache locality and all that stuff isn't really part of algorithmic complexity analysis.
I do like your solution better though, but mostly because it doesn't mutate the array passed to the function. A function called "firstMissingPositive" shouldn't modify state.
Why would set creation (and the not x in b inner loop) take O(Nlog(N)) time? I would have thought it would have just required a hash-lookup for each element (O(1)?) being added (and then, a decision to either add the element or not.
Actual times definitely more than O(N) growth.
Presumably the jump from 100k elements to 1mm elements hit that "cache locality" boundary you were referring to.I'm assuming a set is internally a balanced tree of some sort. So lookup and insertions are O(log N). So N insertions should be O(N log N).
Edit - nevermind. It's a hash table of course. So I'm wrong.
Run this on Python 3 or use xrange instead of range on Python 2 and you get N space instead of 2N anyway :)
Also, the average case for set membership testing is O(1), so the average case runtime would actually be O(N).
https://wiki.python.org/moin/TimeComplexity#set