Time complexity of Java's substring()

java substring time-complexity
TimeToCodeTheRoad picture TimeToCodeTheRoad · Jan 13, 2011 · Viewed 63.1k times · Source

What is the time complexity of the String#substring() method in Java?

Answer

Jon Skeet picture Jon Skeet · Jan 13, 2011

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.

Related questions

Find all possible substring in fastest way

For String A = "abcd" then answer should be {a,ab,abc,abcd,b,bc,bcd,c,cd,d} To find all the substring I have used following method for (int i = 0; i < A.length(); i++) { for (int j = i+1; …

Read More
In Java, how do I check if a string contains a substring (ignoring case)?

I have two Strings, str1 and str2. How do I check if str2 is contained within str1, ignoring case?

Read More
How do I get the last character of a string?

How do I get the last character of a string? public class Main { public static void main(String[] args) { String s = "test string"; //char lastChar = ??? } }

Read More