The time complexity for a code segment

From an online notes, I read the fol开发者_如何学运维lowing java code snippet for reversing a string, which is claimed to have quadratic time complexity. It seems to me that the “for” loop for i just iterates the whole length of s. How does it cause a quadratic time complexity?

public static String reverse(String s)
{
  String rev = new String();
  for (int i = (s.length()-1); i>=0; i--) {
      rev = rev.append(s.charAt(i));
  }
  return rev.toString();
}

public static String reverse(String s)
{
  String rev = " ";
  for (int i=s.length()-1; i>=0; i--)
  rev.append(s.charAt(i); // <--------- This is O(n)
  Return rev.toString();
}

I copy pasted your code. I'm not sure where you get this but actually String doesn't have append method. Maybe rev is a StringBuilder or another Appendable.

Possibly because the append call does not execute in constant time. If it's linear with the length of the string, that would explain it.

append has to find the end of the string, which is Ο(n). So, you have an Ο(n) loop executed Ο(n) times.

I don't think String has an append method. So, this code won't compile.

But, coming to the problem of quadratic complexity, let us assume that you are actually appending the string with a character using '+' operator or the String.concat() method. The String objects are immutable. So, whenever you append to a string, a new string of bigger length is created, old string contents are copied to it and then the final character is appended, and the previous string is destroyed. So, this process takes more and more time as the string grows.

The appending loop takes O(n) time but for every loop you take O(n) time to copy the string character by character. This leads to quadratic complexity.

It would be better to use StringBuilder or StringBuffer. However, I guess the time complexity you mentioned would be with older java compilers. But, new advanced compilers would actually optimize the '+' operation with StringBuilder.