Menu
What is the time complexity of the String#substring() method in Java?
850
You can easily generate substrings of a String using String class substring() method. The time complexity will be O(n)3 since there are two for loops and substring() method has O(n) time complexity.
Whether you use includes, or indexOf — both the naive algorithms take a time complexity of O(m * n), where m is the length of the parent string and n is the length of the substring.
Next let's talk about complexity. In toCharArray(), it takes O(n) time to return the result, where n is the length of the string. It also takes O(n) space as it creates a defensive copy of the original string. In charAt(), it takes O(1) time to return the result as it's a random access.
substring() is blazingly fast. The only thing that would be faster still is to avoid object creation completely by keeping track of the substring start and end positions in variables.
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.
168
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
