CODEWITHSUNDEEP
javastringalgorithmtime-complexity
Jadu Sen
Jadu Sen

Reputation: 391

Time complexity of these 2 program

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?

Upvotes: 1

Views: 170

Answers (2)

Neelesh Salian
Neelesh Salian

Reputation: 119

Forgive the indentation but this is essentially a solution that satisfies the tests.

    public String stringSplosion(String str) {
      // Empty String test
      if (str.length() == 0) 
        return str;

      StringBuilder sb = new StringBuilder();

      for (int i=0; i<=str.length() ; i++) {
        sb.append(str.substring(0,i));
      }
      return sb.toString();
   }

Upvotes: 0

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 235994

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.

Upvotes: 6

Related Questions