Menu
What is the cost / complexity of a String.indexOf() function call?
581
indexOf() – also runs in linear time. It iterates through the internal array and checks each element one by one, so the time complexity for this operation always requires O(n) time.
The complexity of Java's implementation of indexOf is O(m*n) where n and m are the length of the search string and pattern respectively.
The indexOf() method returns the position of the first occurrence of specified character(s) in a string. Tip: Use the lastIndexOf method to return the position of the last occurrence of specified character(s) in a string.
. contains() definitely uses naive approach and equivalent to O(nm) time complexity.
IIRC Java's implementation of .indexOf() is just the naive string matching algorithm, which is O(n+m) average and O(n*m) worst case.
In practice this is fast enough; I tested it for relatively large needle (>500 char) and haystack (few MB) strings and it would do the matching in under a second (in an average household computer). Mind you I forced it to go through the whole haystack.
92
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
