Re^3: Combining arrays with grep/unless?

True, and the OP's isn't really O(N²) either. Both should factor in the length of the string. Both should factor the growth of the array/hash. Mine should also factor in bucket collisions when talking about worst case.

So, the OP's is O(N² * L * O(Growth(N))) and mine is O(N * L * O(Growth(N))). I chose to ignore the common (and thus irrelevant) factor, even if accuracy suffered a little.

Comment on Re^3: Combining arrays with grep/unless?

Replies are listed 'Best First'.
Re^4: Combining arrays with grep/unless? by polettix (Vicar) on Feb 10, 2007 at 01:06 UTC
I think that you're still missing the lookup into the hash, which isn't a constant time operation and can't be factored out because the OP doesn't have it. Since the best you can do with such a lookup is O(log(N)), IMHO the complexity in your case is at least O(N * log(N)). Flavio perl -ple'$_=reverse' <<<ti.xittelop@oivalf Don't fool yourself.	[reply]
Re^5: Combining arrays with grep/unless? by ikegami (Patriarch) on Feb 10, 2007 at 07:18 UTC
Doesn't the number of buckets grow with the number of elements in the hash? If so, why would it take longer as more elements are added? The number of elements in a bucket should remain less than some bound, no? O(bound) = O(1). I don't know how hashes are implemented specifically in Perl, but I heard they were O(1) for lookup. (Again, not worse case.) Wikipedia says the same for hashes in general: Hash tables are often used to implement associative arrays, sets and caches. Like arrays, hash tables provide constant-time O(1) lookup on average, regardless of the number of items in the table. (O(1) means that it takes a constant amount of time independent of the number of items involved.) From where did you get O(log N)?	[reply]
Re^6: Combining arrays with grep/unless? by polettix (Vicar) on Feb 11, 2007 at 15:38 UTC
I was evidently absent at the lessons about hashes, the only things that remained in my memory were the best O(1) and worst O(N), and thougth that the average case should be somewhere in the middle. The O(log N) was there in my head due to binsearch, I presume. Time to eat more fish and improve memory :) Flavio perl -ple'$_=reverse' <<<ti.xittelop@oivalf Don't fool yourself.	[reply]