What is the Big-O of String.contains() in Java?

java string big-o contains
Jason picture Jason · Nov 3, 2010 · Viewed 30.6k times · Source

I'm working on a project, and need to optimize the running time. Is String.contains() runtime the same as TreeSet.contains(), which is O(logN)?

The reason I'm asking is I'm building a TreeMap<String, TreeSet<Song>>, where Songs contain a String of lyrics. Depending on the efficiency, I am considering including a Set of the lyric words inside the Song and running searches on that rather than the String.

Answer

Mark Byers picture Mark Byers · Nov 3, 2010

One of the best known algorithms is the Boyer-Moore string searching algorithm which is O(n) although it can give sublinear performance in the best case.

Which algorithm is used in Java depends on which implemetation you download. It seems that for example OpenJDK uses a naive algorithm that runs in O(nm) and linear performance in the best case. See lines 1770-1806 here.

Related questions

Detecting if a string has unique characters: comparing my solution to "Cracking the Coding Interview?"

I am working through the book "Cracking the Coding Interview" and I have come across questions here asking for answers, but I need help comparing my answer to the solution. My algorithm works, but I am having difficulty understand the …

Read More
How do I convert a String to an int in Java?

How can I convert a String to an int in Java? My String contains only numbers, and I want to return the number it represents. For example, given the string "1234" the result should be the number 1234.

Read More
How to split a string in Java

I have a string, "004-034556", that I want to split into two strings: string1="004"; string2="034556"; That means the first string will contain the characters before '-', and the second string will contain the characters after '-'. I also want to …

Read More