Memory lookup can be considered O(log(m)) where m is the amount of memory you are using. e.g. If the addressable memory space exceeds the word size then it would take two cycles to do a load from memory.<p>In practice memory lookup is O(1) but there is hard limit to the amount that can be used. Except of course this is not true - there are costs to using more memory - because of the cache hierarchy.