On 2/23/12 10:22 PM, Clark Gaebel wrote:
The situation I encounted this is doing a batch update of a map. Is there an easy way to do that? I'm doing something like adding 20-or-so elements to an existing map of a few thousand.
The O(m+n) of the merging functions is actually on the order of the size of the spine intersection between the two maps. Thus, it only ever approaches that limit in cases where the maps are of approximately equal size and are designed for the spines to clash in the worst way. An example would be if you're merging the set of all even numbers and the set of all odd numbers; you have to traverse the whole tree up to the last bit. Ditto for taking the union of a set with itself. When the two maps are of vastly different sizes, O(min(m,n)) is a more intuitive way to think about it. Since you only have to look at the places where the spines clash, that will be on the order of the smaller map. -- Live well, ~wren