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

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 String.length() really walk the whole string just to determine its length?

Solution 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.

Solution 2:

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.

Solution 3:

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)