In Java, for a string x, what is the runtime cost of s.length()? Is it O(1) or O(n)?

Question

I've been told that code such as:

for (int i=0; i<x.length(); i++) {
    // blah
}

is actually O(n^2) because of the repeated calls to x.length(). Instead I should use:

int l=x.length();
for (int i=0; i<l; i++) {
    // blah
}

Is this true? Is string length stored as a private integer attribute of the String class? Or does length() really walk the whole string just to determine its length?

Answer 1

No, the length of a java string is O(1) because java's string class stores the length as a field.

The advice you've received is true of C, amongst other languages, but not java. C's strlen walks the char array looking for the end-of-string character. Joel's talked about it on the podcast, but in the context of C.

Answer 2

According to this, the length is a field of the String object.

Answer 3

I don't know how well the link will translate, but see the source of String#length. In short, #length() has O(1) complexity because it's just returning a field. This is one of the many advantages of immutable strings.

Answer 4

Contrary to what has been said so far, there is no guarantee that String.length() is a constant time operation in the number of characters contained in the string. Neither the javadocs for the String class nor the Java Language Specification require String.length to be a constant time operation.

However, in Sun's implementation String.length() is a constant time operation. Ultimately, it's hard to imagine why any implementation would have a non-constant time implementation for this method.

Answer 5

You should be aware that the length() method returns the number of UTF-16 code points, which is not necessarily the same as the number of characters in all cases.

OK, the chances of that actually affecting you are pretty slim, but there's no harm in knowing it.

Answer 6

String stores the length in a separate variable. Since string is immutable, the length will never change. It will need to calculate the length only once when it is created, which happens when memory is allocated for it. Hence its O(1)

Answer 7

In the event you didn't know you could write it this way:

for (int i=0, l=x.length(); i<l; i++) {
  //blah
}

It's just slightly cleaner since l's scope is smaller.