Time complexity of Java's substring()

New answer

As of update 6 within Java 7's lifetime, the behaviour of substring changed to create a copy - so every String refers to a char[] which is not shared with any other object, as far as I'm aware. So at that point, substring() became an O(n) operation where n is the numbers in the substring.

Old answer: pre-Java 7

Undocumented - but in practice O(1) if you assume no garbage collection is required, etc.

It simply builds a new String object referring to the same underlying char[] but with different offset and count values. So the cost is the time taken to perform validation and construct a single new (reasonably small) object. That's O(1) as far as it's sensible to talk about the complexity of operations which can vary in time based on garbage collection, CPU caches etc. In particular, it doesn't directly depend on the length of the original string or the substring.

It was O(1) in older versions of Java - as Jon stated, it just created a new String with the same underlying char[], and a different offset and length.

However, this has actually changed started with Java 7 update 6.

The char[] sharing was eliminated, and the offset and length fields were removed. substring() now just copies all the characters into a new String.

Ergo, substring is O(n) in Java 7 update 6

It's now linear complexity. This is after fixing a memory leak issue for substring.

So from Java 1.7.0_06 remember that String.substring now has a linear complexity instead of a constant one.