Time complexity of Java’s substring()

by

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.

More Related Contents:

  1. O(3^n) exponential time complexity [closed]
  2. Showing the order of growth of the function
  3. Need the words between the ” – ” ONLY string splitting [duplicate]
  4. Can you explain the output of the following source code?
  5. Is a Java hashmap search really O(1)?
  6. How to find nth occurrence of character in a string?
  7. In Java, how do I check if a string contains a substring (ignoring case)? [duplicate]
  8. How to replace case-insensitive literal substrings in Java
  9. Java: Getting a substring from a string starting after a particular character
  10. Java – removing first character of a string
  11. How does Java store Strings and how does substring work internally? [closed]
  12. Time complexity for java ArrayList
  13. Why is “out of range” not thrown for ‘substring(startIndex, endIndex)’
  14. What are the time complexities of various data structures?
  15. String concatenation complexity in C++ and Java [duplicate]
  16. What is the time complexity of HashMap.containsKey() in java?
  17. substring index range
  18. How to replace a substring of a string [duplicate]
  19. What is the complexity of this simple piece of code?
  20. String index out of bounds exception java
  21. LRU cache in Java with Generics and O(1) operations
  22. How do I get the last character of a string?
  23. Finding second occurrence of a substring in a string in Java
  24. Time complexity of contains(Object o), in an ArrayList of Objects
  25. Java Math.pow(a,b) time complexity
  26. Time complexity of System.arraycopy(…)?
  27. Java, how to draw constantly changing graphics
  28. Setting the maximum size of a JDialog?
  29. How to round up the result of integer division?
  30. Spring data JPA and parameters that can be null

Leave a Comment