8 Nov
2006
8 Nov
'06
4:56 p.m.
Sebastian Redl wrote:
doing an array lookup is O(n). Huh? Array indexing is constant time. The compiler doesn't scan the array, it uses the switch value directly as the index (after some mathematical
james.jones@firstinvestors.com wrote: transformation, perhaps.)
I think I see where the confusion came from: poor wording on my part. In step three, where I talk about "looking stuff up" in the arrays, I meant to say the array is indexed by the stuff, not that the runtime must search for it. The lookup, in this case, is a simple indexing operation, and is often implemented in one or two machine instructions.