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

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?

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

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 by JW. for In Java, for a string x, what is the runtime cost of s.length()? Is it O(1) or O(n)?

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

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

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 by Alexander for In Java, for a string x, what is the runtime cost of s.length()? Is it O(1) or O(n)?

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 by Marcus Downing for In Java, for a string x, what is the runtime cost of s.length()? Is it O(1) or O(n)?

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 by Satish for In Java, for a string x, what is the runtime cost of s.length()? Is it O(1) or O(n)?

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 by Allain Lalonde for In Java, for a string x, what is the runtime cost of s.length()? Is it O(1) or O(n)?

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.

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72