in reply to Re: using hash uniqueness to find the odd man
in thread using hash uniqueness to find the odd man
If the two lists of DNs are sorted initially, you can use a merge algorithm (as in the unix comm program). That is an optimal solution, because it takes O(@a + @b) time, and there's no way to solve the problem without examining everything in both lists. If you have to sort the lists first, that's more expensive than the hash method.
Update: Now that I'm getting analysis of algorithms paged back in, I'm thinking A should have been @a in the first paragraph. The hashtable has to expand about log(@a) times, but each time it only has to reconsider the elements that were previously inserted, so it's @a + @a/2 + @a/4 + ... = @a*2, which is proportional to @a.
|
|---|
| Replies are listed 'Best First'. | |
|---|---|
|
Re: Re: Re: using hash uniqueness to find the odd man
by tachyon (Chancellor) on Jul 11, 2001 at 05:26 UTC |