java - What is the cost / complexity of a String.indexOf() function call

Question

What is the cost / complexity of a String.indexOf() function call?

Answer 1

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.