Do String methods in Java run in O(1) time?

Question

This is my code to find the length of the longest substring without repeating characters. Does this code run in O(n) time? Or does it run in O(n^2) time? I am not sure if the String methods run in O(n) time or O(1) time.

A test case includes: "pwwkewo" returning 4 because "kewo" is the the longest substring inside the string that has unique characters.

public int lengthOfLongestSubstring(String s) {

    int maxLength = 0;
    String sub = "";

    for(int i=0; i<s.length(); i++) {

         //add that char to the sub string
         sub = sub + s.charAt(i);

        //if we find a char in our string
        if(sub.indexOf(s.charAt(i)) != -1) {

           //drop any replicated indexes before it
            sub = sub.substring(sub.indexOf(s.charAt(i)) + 1);
        }

        if(sub.length() > maxLength) {
            maxLength = sub.length();
        }


    }

    return maxLength;

}

i'd guess its O(n) because the more characters you have, the longer it takes — XtremeBaumer, Dec 14 '17 at 08:27
Won't it be O(N^2) because `sub.indexOf()` is O(N)? BTW, `sub = sub + s.charAt(i);` makes for a very inefficient loop as there's a lot of excess memory allocation - look at `StringBuilder` instead. — Ken Y-N, Dec 14 '17 at 08:28
Depends on your Java version. Check https://stackoverflow.com/questions/4679746/time-complexity-of-javas-substring — SaiBot, Dec 14 '17 at 08:28

score 7 · Answer 1 · answered Dec 14 '17 at 08:32

sub.indexOf() can take linear time, since it might have to check all the characters of sub. And the length of sub is O(n) in the worst case (assuming your input has no repeating characters).

Therefore your total running time is O(n²), since the loop has n iterations and in each iteration you call indexOf().

score 1 · Answer 2 · answered Dec 14 '17 at 08:33

1

Your code runs in O(n^2) as there is a for loop and inside it you call an indexOf() method. This in turn is O(n).

Thus your method is O(n^2).

answered Dec 14 '17 at 08:33

Pritam Banerjee

17,953
10
93
108

And there are more O(n) operations in the loop: `sub = sub + s.charAt(i);` (better use `StringBuilder`), `sub.substring(...)` (in later Java releases, this creates a copy of the characters). And doing `sub.indexOf(s.charAt(i)` twice also is a waste of time, but doesn't influence the Big-O classification. – Ralf Kleberhoff Dec 14 '17 at 10:36

Do String methods in Java run in O(1) time?

2 Answers2