# 问题内容:

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?

# 答案:

## 答案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.

## 原文地址：

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