performance of get the length of a string in Python 2.7

Question

When calling len("1234567890"), the performance is constant i.e. O(1), or linear to the length of the string, i.e. O(n) according to the length of the string (in this example, the length of the string is n=10)? If constant performance, why? And if linear performance, any ideas how to improve performance of getting the length of a string? Thanks.

Using Python 2.7.

regards, Lin

• Burhan Khalid: What is the problem you are trying to solve?
• Moon Cheesez: It is O(1) as mentioned here: stackoverflow.com/questions/1115313/cost-of-len-function Why? I'll leave that for someone else.

Answer 1

Check it:

C:\>py -m timeit -s "x='a'*1000" "len(x)"
10000000 loops, best of 3: 0.0959 usec per loop
C:\>py -m timeit -s "x='a'*10000" "len(x)"
10000000 loops, best of 3: 0.0902 usec per loop
C:\>py -m timeit -s "x='a'*100000" "len(x)"
10000000 loops, best of 3: 0.0927 usec per loop

It's O(1). The size of the string is stored in the object when it is created.

• Moon Cheesez: This reminds me of assembly where you had to store the length of strings for uses such as printing to stdout.
• Mark Tolonen: @MoonCheesez, it's all convention. I could write assembly that uses nul-terminated strings instead, but it would be O(n) instead for getting length.
• Lin Ma: Thanks Mark, excellent reply, vote up and mark your reply as answer.