Complexity of finding all substrings of a string

Question

Here is a solution for finding all substrings of a string.

for (int i = 0; i < str.length(); i++) {
    String subStr;
    for (int j = i; j < str.length(); j++) {
        subStr = str + str.charAt(j));
        System.out.println(subStr);
    }
}

All over the internet I read that the complexity of this code is O(n²). However the + operation is an O(n) operation. Thus in my opinion the complexity should be O(n³).

In case I am wrong, please correct my understanding.

Don't use `+`. Use `StringBuilder` instead. – Maroun Jul 07 '13 at 09:37 — Maroun, Jul 07 '13 at 09:37

score 2 · Accepted Answer · edited Jul 07 '13 at 09:36

2

Adding a character to a string is a O(1) operation. You get O(n³) if you take into account also the time need to print the output with println.

edited Jul 07 '13 at 09:36

Maroun

94,125
30
188
241

answered Jul 07 '13 at 09:36

Emanuele Paolini

9,912
3
38
64

"Adding a character to a string is a O(1) operation" : this is incorrect, since String is immutable, the concatenation happens in O(n) time. You could use a StringBuilder instead which would have O(1) time. – Vyshnav Ramesh Thrissur Feb 10 '20 at 08:17
@VyshnavRameshThrissur are you sure? This depends on internal implementation. Tha java compiler might (and should) notice that the old value is discarded and hence make the character addition in place. – Emanuele Paolini Feb 11 '20 at 11:24
Yes. https://stackoverflow.com/questions/15400508/string-concatenation-complexity-in-c-and-java https://stackoverflow.com/questions/4323018/is-more-efficient-than-concat In short, during addition of two strings, a new StringBuilder is created. The first string chars are copied into this and the second string chars are appended to this. This is then converted to a string using toString() and returned. – Vyshnav Ramesh Thrissur Feb 12 '20 at 12:26

nullptr · Answer 2 · 2013-07-07T09:42:58.270

1

Finding all substrings of a string is O(n²) (by finding a substring I mean determining its begin and end indexes), it's easy to see because the total number of substrings is O(n²).

But printing all of them out is O(n³), simply because total number of characters to be printed is O(n³). In your code, println adds O(n) complexity (the + operator should have O(1) complexity if used/implemented properly).

edited Jul 07 '13 at 09:42

answered Jul 07 '13 at 09:36

nullptr

11,008
1
23
18

score 1 · Answer 3 · answered Jul 07 '13 at 10:12

Finding all substrings from a string the naive way is indeed O(n^2). But the code in the question doesn't probably do that. Here is the corrected version.

    for (int i = 0; i < str.length(); ++i) {
        //Initialize with max length of the substring 
        StringBuilder prefix = new StringBuilder(str.length() - i);
        for (int j = i; j < str.length(); ++j) {
            prefix.append(str.charAt(j)); //this step is O(1).
            System.out.println(prefix); //this step is supposed to be O(1)
        }
    }

The total number of iterations is given by
Outer Loop  : Inner Loop
First time  : n
Second time : n - 1
Third Time  : n - 2
..
n - 2 time  : 2
n - 1 time  : 1 



So the total number of iterations is sum of iterations of outer loop plus sum of iterations of the inner loop.
n + (1 + 2 + 3 + ... + n - 3 + n - 2 + n - 1 + n) is  = O(n^2)

Complexity of finding all substrings of a string

3 Answers3