> (A constant amount is of course independent of N anyway!)
When using O notation, we're doing asymptotic analysis and n can be arbitrarily large. If you have an arbitrarily large pointer, you cannot store the pointer in a constant number of bits. If your pointer is 64-bits long, you're cannot handle n > 2^64. That is why I said you need O(log n) rather than O(1).
If you can use templates, the decision of which function to call can be done at compile time and you don't need virtual calls. Virtual calls are useful when the decision must be done at runtime.