51 ms·
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 spa
by gizmo 12y ago
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.
- ghshephard 12y agoWhy 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.
- gizmo 12y agoI'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.
- michaelmior 12y agoRun 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 https://wiki.python.org/moin/TimeComplexity#set