title: What is the Big-O of String.contains() in Java?
body: <p>I'm working on a project, and need to optimize the running time.  Is <code>String.contains()</code> runtime the same as <code>TreeSet.contains()</code>, which is O(logN)?</p>
  
  <p>The reason I'm asking is I'm building a <code>TreeMap&lt;String, TreeSet&lt;Song&gt;&gt;</code>, 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.</p>