CODEWITHSUNDEEP
javabig-ostringbuilder
Louis Tran
Louis Tran

Reputation: 1156

Big O of String repetition append in Java

I have a function to get a a string as a repetition of an original string. I'm wondering if I use StringBuilder append, what is the Big O of the function? Is it O(nl) : n is number of repeats and l is length of the original string ?

public String getRepetition(String originalStr, Integer n){
    StringBuilder str = new StringBuilder();
    for(int i = 0; i < n; i++)
        str.append(originalStr);
    return str.toString();
}

Comparing with the approach below, which one is better?

public String getRepetition(String originalStr, Integer n){
    String str = "";
    for(int i = 0; i < n; i++)
        str += originalStr;
    return originalStr;
}

Upvotes: 0

Views: 277

Answers (3)

Tom Hawtin - tackline
Tom Hawtin - tackline

Reputation: 147164

I'm not sure why other three answers are all saying both pieces of code are O(n). Assuming originalStr is not "", the first is O(n) the other O(n^2)! (That's an exclamation, not a factorial.) They teach this on the first day of Java school. C programmers get "don't use strlen in the condition of that for loop"; Java programmers get this.

String str = "";
for(int i = 0; i < n; i++)
    str += originalStr;

Each time around this loop str is getting longer. It's i * orginalStr.length(). Creating a new String (assuming no wild compiler optimisations) which takes time roughly proportional to i each time.

Edit: Usually we ignore the length of the original string. But yeah, of course it's going to be proprotional, so O(nstrlen(originalStr)) and O(nn*strlen(originalStr)). By convention this is dealt with separately.

If we rewrite the code without the String abstraction, perhaps it will be clearer.

public static char[] getRepetition(char[] originalStr, int n) {
    char[] str = {};
    for (int i = 0; i < n; ++i) {
        assert str.length == i * originalStr.length;
        char[] newStr = new char[str.length + originalStr.length];
        for (int j=0; j<str.length; ++j) {
            newStr[j] = str[j];
        }
        for (int j=0; j<originalStr.length; ++j) {
            newStr[str.length+j] = originalStr[j];
        }
        str = newStr;
    }
    return str;
}

(As ever, I've not bothered to so much as compile the code. Not safe to use in a nuclear reactor.)

Just for giggles, let's deabstract the first implementation.

public static char[] getRepetition(char[] originalStr, int n) {
    char[] str = new char[16];
    int strLen = 0;
    for (int i = 0; i < n; ++i) {
        assert strLen == i * originalStr.length;
        // ensureCapacity
        if (str.length < strLen + originalStr.length) {
            // The size at least doubles, 
            //   so this happens increasing less often.
            // It wont happen again for approximately
            //   the same number of iterations
            //   as have already happened!
            char[] newStr = new char[Math.min(
                str.length + originalStr.length, // first time safe
                str.length*2 + 2                 // *2 !
            )];
            for (int j=0; j<strLen; ++j) {
                newStr[j] = str[j];
            }
            str = newStr;
        }
        // actual append
        for (int j=0; j<originalStr.length; ++j) {
            str[strLen++] = originalStr[j];
        }
    }
    // toString
    char[] newStr = new char[strLen];
    for (int i=0; j<newStr.length; ++i) {
         newStr[i] = str[j];
    }
    return newStr;
}

Upvotes: 3

Elliott Frisch
Elliott Frisch

Reputation: 201457

Both of your approaches are O(n) while the first approach eliminates several temporary String(s). It isn't clear why you have made n an Integer, nor why you have not made this a static method (it depends on no instance state). Additionally, in Java 8+, you could implement it with a lambda like

public static String getRepetition(String originalStr, int n) {
    return Stream.generate(() -> originalStr).limit(n).collect(Collectors.joining());
}

Also, if you're going to use a StringBuilder as in your first example, you can explicitly size it to avoid having to amortize the cost of resizing the StringBuilder

StringBuilder str = new StringBuilder(originalStr.length() * n);

Upvotes: 2

Shubhendu Pramanik
Shubhendu Pramanik

Reputation: 2751

In both the cases the complexity is O(n) because you are iterating n times.

The only difference in second approach is you are creating new String in each iteration i.e. at str += originalStr;

Upvotes: 1

Related Questions