34

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?

Augustin
  • 2,444
  • 23
  • 24
someguy
  • 1,923
  • 5
  • 21
  • 19
  • 1
    Even if calculating the length of the string was O(n), the total complexity would still not be O(n^2). The length is calculated once and is used as the boundary value in the for loop, it isn't calculated on each iteration. – Mark S. Rasmussen Oct 31 '08 at 20:06
  • 1
    As far as I know, boundary values are not cached. What if the boundary were to be modified in the loop? – Michael Myers Oct 31 '08 at 20:08
  • 3
    The boundary is calculated every time. Remember, the for loop's check is just an arbitrary expression. The compiler doesn't really care what's in there, and can't make assumptions. You could easily be calling a method that returns something different every time. – Herms Oct 31 '08 at 20:23
  • 1
    Boundary values can be cached in certain cases. For instance, the JIT compiler knows what arrays are like, and if it can determine that the variable itself isn't going to change during a loop, it knows that the vaue of foo.length isn't going to change. I don't know if it does the same for strings. – Jon Skeet Oct 31 '08 at 20:25
  • In his example, x is a String reference, which could be made to point to a different String object inside the loop. In that case, the boundary needs to be recalculated every time. I don't know if the JIT is smart enough to check if the reference itself is reassigned. Probably. – Bill the Lizard Oct 31 '08 at 20:30
  • Even so, the complexity of the first example has an upper bound of n^2. – Bill the Lizard Oct 31 '08 at 20:31

8 Answers8

60

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.

sblundy
  • 60,628
  • 22
  • 121
  • 123
  • Note that the code will still execute the method call on each iteration (the compiler doesn't know the value won't change). Moving the call outside the loop control will eliminate the method call. Having said that, it isn't likely that will cause much change in the execution time of this loop – Ken Gentle Oct 31 '08 at 20:20
  • 5
    A modern JIT will probably notice that length() is a simple getter of a final class returning a final primitive value and replace the method call with the int value itself. – sk. Oct 31 '08 at 20:25
  • sk--I seem to recall seeing a blog that tested the JIT optimization of length() and proved it was true. – James Schek Oct 31 '08 at 21:07
  • 1
    Since JDK9 this is no longer true: char array has been changed to byte array, so the length() implementation now require bit-shift operation. We found some regression due to length() being called multiple times. – Bùi Anh Dũng Oct 04 '21 at 03:23
14

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.

Alexander
  • 9,302
  • 2
  • 26
  • 22
  • 2
    Not withstanding, I think that it is safe to *assume* that String.length *will always* be constant time ... for the reasons that you have given. – Stephen C Jul 15 '12 at 12:05
9

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)

Satish
  • 1,883
  • 3
  • 15
  • 18
5

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.

Augustin
  • 2,444
  • 23
  • 24
Allain Lalonde
  • 91,574
  • 70
  • 187
  • 238
4

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.

Marcus Downing
  • 10,054
  • 10
  • 63
  • 85
  • http://java.sun.com/javase/6/docs/api/java/lang/Character.html#unicode Basically, some characters have to be represented by two char values. Since length() is the size of the char[] array, it might not be the same as the number of characters. But, as sadie said, that's very rare. – Alan Moore Nov 02 '08 at 12:52
0

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.

Daniel Spiewak
  • 54,515
  • 14
  • 108
  • 120
  • Immutability doesn't have anything to do with it. You can have a mutable string class that keeps track of its length, just the same as you can with an immutable string (for instance, StringBuilder). And you can have an Immutable string that doesn't (const char* in C). – Herms Oct 31 '08 at 20:08
  • But immutability does guarantee that you only have to calculate the value for length once when the object is created. If the object were mutable it would require a new calculation for every invocation of a mutator method. Pay me now or pay me later as the saying goes. – laz Oct 31 '08 at 20:43
  • 1
    Strictly speaking, you're both right; but concurrency throws a wrench into the whole affair. Trying to keep an ancillary field updated as the data structure changes asynchronously is essentially impossible, so often length() is computed rather than accessed in mutable String implementations. – Daniel Spiewak Nov 01 '08 at 02:06
  • You are absolutely correct and I left that important detail out. Oops! – laz Nov 05 '08 at 21:07
0

No worries even though we are calling length() as a method on x.length(), Actually length is stored as a field/property in String class and this field/property returned by length() method whenever we call " x.length()".

Check out this image link or below code snippet of length() method defined in String class-

ImageLink

public int length() {
    return value.length >> coder();
}

length() method returns the length property which is already stored in String class.

Revanth Reddy Datla
  • 1
-2

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

JW.
  • 50,691
  • 36
  • 115
  • 143