Coste de la funcion len() en los strings de Python

Sospechaba que el coste era constante, y según me han comentado así es. Se fija durante la creación de los string, ya que éstos son inmutables.

Su implementación se puede ver aquí.
Y muy interesante la intervención de Alvaro Leiva, en la lista python-es, sobre el modulo timeit (disponible a partir de Python 2.3):

Aparentemente el coste no depende de el tamaño de un string.

En todo caso puedes verlo tu enpiricamente con este programita

from timeit import Timer


x=["a"*10,"a"*100,"a"*1000,"a"*10000]

for i in x*5:
  print Timer("len(x)","x='%s'" % i).timeit()

Te daras cuenta que casi siempre te imprime el mismo numero "0.55" en mi
computador....

Esto deja en claro que el coste no depende de el largo del string. No asi
cuando uno ejecuta esto con listas

x=[["a"]*10,["a"]*100,["a"]*1000,["a"]*10000]

for i in x*5:
  print Timer("len(x)","x=%s" % i).timeit()

Que arroja siempre valores pequeños de tiempo para ["a"]*10 y los tiempos
siempre son acendentes....

Este metodo del from timeit import Timer siempre lo ocupo cuando tengo una
duda sobre el coste de una funcion... Muy util cuando uno programa
algoritmos de optimisacion lineal como el simplex... Algoritmos famosos por
su tendencia a volverse lentos