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.

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