What is the BigO notation on searching on a string that keeps changing for a character

user_1077748 0
Viewed 192

I have the function below that finds the longest non repeating sub-string in a string. I know the for loop is O(n) but what will be the additional time by searching current char in tmp string in call to function indexOf.

public static String find(String input) {
    String currentLongest = input.length() > 0 ? "" + input.charAt(0) : "";
    String tmp = currentLongest;
    for (int i = 1; i < input.length(); i++) {
        int index = tmp.indexOf(""+input.charAt(i));
        if (index  == -1) {
            tmp = tmp + input.charAt(i);
            if (tmp.length() > currentLongest.length())
                currentLongest = tmp;
        } else
            tmp = tmp.substring(index+1)+input.charAt(i);
    }
    return currentLongest;
}
big-o time-complexity algorithm java string
1 Answers

Both indexOf(), and recreating tmp (using operator+), which both happen in every iteration, takes O(|S|) time, where |S| is the length of tmp in this iteration. Now, the question is is the length of tmp bounded?

If your alphabet is limited (for example, if it can contain only characters from a,b,...,z) - then the length of tmp is of limited size (26 in the a-z example, this comes from pigeonhole principle). In this case, you can say that indexOf() and creating a new string (by using operator +) is taking O(1) time, since it is creating a string with bounded size. And in this case, the algorithm takes O(n) time.

However, if the alphabet is unlimited, you can have an input string with no repeatitions at all. In this case, each iteration of the loop takes O(i) time. This gives you.

1 + 2 + ... n = n (n+1)/2

Which is in O(n^2), and the algorithm's complexity becomes O(n^2)

user_5726700
Related