It was probably true.  The issue is how well the words self-separate
visually and whether an underscore would create a detrimental mental
pause.  So fromkeys() and fromhex() read fine and would feel awkward
with an underscore.  But bitlength causes me a mental double-take when
my mind searches for the word separation.  It that case, PEP 8 suggests
that an underscore be added for clarity.  This is probably why
Mathematica chose BitLength in titlecase instead of Bitlength.  Logic
aside, bit_length() just looks and feels better to me.

Did you look at the O(lg n) algorithm yet?  Any thoughts?