On Sat, 12 Apr 2003 14:31:52 +0300, "Berk D. Demir" wrote: > > >from previous discussion I recall it was O(1) ie. constant time for each > > >address family. Which is _much_ better than O(log n). > > > > > Well, I don't know exactly, but it's certainly *not* O(1), that I'm sure. > > If its O(log n) or O(log log n) or whatever in between, I'm don't know. > > > As far as I know, Patricia Trees work by inserting bits into nodes by > level. > > For example: > . > / \ > 0 . > \ \ > . 11 > / \ > 010 011 > > As seen in the figure, some nodes maybe empty depending on your set. > > The tree height for IPv4 addresses will be 32 and 128 for IPv6. > By making at most 32 or 128 comparisons you'll locate your address. > This seems to me a O(1) situation.
Yes, but we can get a better bound than that. Remember that being O(f(n)) means that the quantity we're measuring (in this case time of lookups) is bounded by some constant factor times f(n), where n is some variable quantity (in this case, addresses). Since there's a fixed maximum number of nodes (because there's a fixed maximum number of IPv4 or IPv6 addresses), any correct algorithm is O(1), but it may have a really big constant in front of it. A better bound is O(log(n)) (I think--I've never quite understood Patricia trees), because the constant factor that O ignores is much smaller. This is really a shortcoming of O notation; it's easier to understand a comparison like this when you try to work out rough running times using each bound. -- Kyle R. Hofmann <[EMAIL PROTECTED]>
