In the correct interpretation, 'n' is the number of possible [inputs]
Ahh. That makes sense. For some reason I always thought of n as the number of possible outputs. Thanks for setting me straight. I guess V5 is a binary search! :)
Another bold statement.
That was an aside: as I already admitted, if we know that the distribution will be perfectly random, we'd be better served by V5 than V4.
If we don't know the distribution of inputs or the performance expectations, I maintain that it's best to offer reasonable and similar performance for all inputs. This cuts down on difficult to find performance degradation in production code. Optimization can come later (after profiling), if it's necessary at all.
In fact for the average case, NextPowerV5() performance is constant time - O(1)
Now you're just being silly.