> 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.
I completely agree with you. While I was writing to explain myself, your message arrived. Although the complexity of algorithm is O(1), the constant 32 can be a huge constant to name it "constant time". Since O-notation describes an upper bound, when we use it to bound the worst-case running time of an algorithm, by implication we also bound the running time of an algorithm on arbitrary inputs as well. For example, in insertion sort O(n^2) worst-case applies to it's running time in every input. Theta(n^2) bound on the worst-case running time of insertion sort doesn't imply a Theta(n^2) for *every* input. The running time will be Theta(n) if the input to insertion sort is already sorted. So it's the same in our topic too. The worst case Theta(log n) when n equals to 4 billions isn't always the worst case because you don't need 4 billions of addresses to create the worst case. You can do it with less addresses. Also you can still get a very short running time with thousands of addresses (specialy selected) Let's finish this useless discussion (/academic masturbation) here. Like Theo says, "shut up and hack!" Cheers, -bdd
