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