# 问题内容:

I am new to complexity analysis. The task is that given a non-empty string like “Code” return a string like “CCoCodCode”. I have these 2 programs which are doing the same thing.

Program 1:

``````public String stringSplosion(String str) {
String result = "";
for (int i=0; i<str.length(); i++) {
for(int j=0;j<=i;j++)
result += str.charAt(j);
}
return result;
}
``````

So, above one is pretty simple and this program has O(n^2) complexity.

Program 2:

``````public String stringSplosion(String str) {
String result = "";
// On each iteration, add the substring of the chars 0..i
for (int i=0; i<str.length(); i++) {
result = result + str.substring(0, i+1);
}
return result;
}
``````

From a different StackOverflow question, it seems `str.substring()` has a time complexity of O(n). In that case, program 2 also has O(n^2) time complexity.

Is my analysis correct or I am missing something?

## 问题评论:

Yes, you’re right.
Well even more, you can make it a bit faster (but still O(n^2)) by using a StringBuilder instead of the string concatenation. Btw. all Algorithms solving this problem have at least O(n^2) time complexity since the output has length O(n^2).
I think you are right. You can always test execution times with really long strings. For example, if you go from length=1000 to length=2000, does execution time increase with a factor 4 for both methods?

# 答案:

## 答案1:

In fact, both have the same complexity – `O(n^3)`. That’s because you’re using `+=` for concatenating the answer! there’s a hidden loop there that you didn’t account for, and a classic example of Schlemiel the Painter’s Algorithm. You should use `StringBuilder` instead, it’s the right way to build a string as you go.

## 答案评论:

@Stefan Indeed! There’s the explicit loop, and the loop in the `substring` operation, and finally the loop in the `+` concatenation operation
While this is a good observation, the compiler will convert his string concatenation to a StringBuilder internally. docs.oracle.com/javase/specs/jls/se8/html/…
Yes, but not necessarily an useful one. It depends on where itâs declared – inside or outside the loops

## 原文地址：

https://stackoverflow.com/questions/47755613/time-complexity-of-these-2-program