String, StringBuilder and StringBuffer class methods

1. reverse() method of StringBuilder and StringBuffer class in JAVA
NOTE: This method is NOT present in String class
NOTE: reverse() method is an instance method of StringBuilder class AND
reverse() method is also an instance synchronized method of StringBuffer class in JAVA

PLEASE NOTE THAT reverse() method is NOT PRESENT in String class of JAVA. The reason being String class
in JAVA is immutable. However, for some reason substring() method is present in String class even though String 
is immutable in JAVA. Also StringBuilder and StringBuffer classes each have substring() method.

Source: http://stackoverflow.com/questions/19814067/time-complexity-of-stringbuilder-reverse-method
Solution: It is O(n). It is impossible to revert a String in less than O(n)

2. toCharArray() and toString() methods
NOTE: toCharArray() method is ONLY present in String class & NOT present in StringBuilder and StringBuffer classes.
toString() method is present in all three classes, String, StringBuilder and StringBuffer classes.
Source: http://stackoverflow.com/questions/13079261/what-is-the-runtime-of-tochararray-and-tostring-in-java
Solution:
As far as String.toCharArray() goes, it's O(N), where N is the number of characters in the string,
because each character must be copied into the output.
toString() is O(N) time complexity.
The toString() method is implemented using System.arrayCopy, which happens to be a native method.
I would imagine that the native method probably uses memcpy under the hood which is O(N), so the runtime O
is dependent on the actual jvm implementation. You might take a look at the open jdk source to check the 
source for this native method.

3. substring() method of String, StringBuilder and StringBuffer classes
NOTE: substring() method is present in all three classes, String, StringBuilder and StringBuffer classes.
Answer: The time compexity of substring() method in all three classes is O(n)
Question: What is the time complexity of the following program ?

public static void calculateTimeComplexity(String s){
  for(int i=0;i<s.length();i++){
    for(int j=i;j>=0;j--){
      System.out.println(s.substring(j,i+1));
    }
  }
}

Options: 1. O(n^2)
         2. O(n^3)
where n = length of the string


Solution:

Answer is option 2. O(n^3)

Source: http://stackoverflow.com/questions/4679746/time-complexity-of-javas-substring
        http://stackoverflow.com/questions/16123446/java-7-string-substring-complexity
        http://stackoverflow.com/questions/25514062/what-is-the-time-complexity-of-java-stringbuilder-substring-method-if-it-is-l

Explanation:
It was O(1) in older versions of Java - it just created a new String with the same underlying char[],
and a different offset and length.
However, this has actually changed started with Java 7 update 6.
The char[] sharing was eliminated, and the offset and length fields were removed. substring() now just copies all the 
characters into a new String.
Ergo, substring is O(n) in Java 7 update

4. indexOf() method of String, StringBuilder and StringBuffer classes
NOTE: indexOf() method is present in all three classes, String, StringBuilder and StringBuffer classes.
Source: http://stackoverflow.com/questions/12752274/java-indexofstring-str-method-complexity
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.
What you can do to improve complexity is to use e.g., the Boyer-More algorithm to intelligently skip comparing
logical parts of the string which cannot match the pattern.

5. charAt() and deleteCharAt() of String, StringBuilder and StringBuffer classes
NOTE: charAt() method is present in all three classes, String, StringBuilder and StringBuffer classes.
deleteCharAt() method is present in StringBuilder and StringBuffer classes. It is not present in String class. 
Question:
I've been wondering about the implementation of charAt function for String/StringBuilder/StringBuffer
in java what is the coomplexity of that ? also what about the deleteCharAt() in StringBuffer/StringBuilder ?
Source: http://stackoverflow.com/questions/6461402/java-charat-and-deletecharat-performance
Solution: 
The charAt method is O(1).
The deleteCharAt method on StringBuilder and StringBuffer is O(N) on average, assuming you are deleting a
random character from an N character StringBuffer / StringBuilder. (It has to move, on average, 
half of the remaining characters to fill up the "hole" left by the deleted character.
There is no amortization over multiple operations; see below.) However, if you delete the last character,
the cost will be O(1).
There is no deleteCharAt method for String.
For String, StringBuffer, and StringBuilder, charAt() is a constant-time operation.
For StringBuffer and StringBuilder, deleteCharAt() is a linear-time (i.e. O(n)) operation, and NOT constant time operation.
StringBuffer and StringBuilder have very similar performance characteristics.
The primary difference is that the former is synchronized (so is thread-safe) while the latter is not.


6. equals() method
Source: http://stackoverflow.com/questions/14552285/what-is-the-time-complexity-of-equals-in-java-for-2-strings
NOTE: equals() is a method of Object class. So ALL CLASSES AND INTERFACES in Java have equals() method
Hence no question arises that whether String, StringBuilder, StringBuffer OR all three classes has equals() method
because ALL CLASSES AND INTERFACES in Java have equals() method
Worst case is O(n), unless the two strings are the same object in which case it's O(1).
(Although in this case n refers to the number of matching characters in the two strings starting
from the first character, not the total length of the string).
This is easily possible in O(n), and impossible in less than that, so that's what it should be.