Is the time complexity of this code O(N^2)

Question

This is a solution of mine for one of the problems in leetcode. Through my deductions, I concluded it to have an overall O(N^2) time complexity. However, I would like to get a confirmation on this just so that I don't continue making the same mistakes when it comes to judging the time/space complexity of an algorithm.

Oh, and the problem goes as follows:

Given an input string, reverse the string word by word. e.g. "I am you" == "you am I"

The code is as follows:-

public String reverseWords(String s) {
        //This solution is in assumption that I am restricted to a one-pass algorithm.
        //This can also be done through a two-pass algorithm -- i.e. split the string and etc.

        if(null == s)
            return "";
        //remove leading and trailing spaces
        s = s.trim();
        int lengthOfString = s.length();
        StringBuilder sb = new StringBuilder();
        //Keeps track of the number of characters that have passed.
        int passedChars = 0;
        int i = lengthOfString-1;
        for(; i >= 0; i--){
            if(s.charAt(i) == ' '){
                //Appends the startOfWord and endOfWord according to passedChars.
                sb.append(s.substring(i+1, (i+1+passedChars))).append(" ");
                //Ignore additional space chars.
                while(s.charAt(i-1) == ' '){
                    i--;
                }
                passedChars = 0;
            }else{
                passedChars++;
            }
        }

        //Handle last reversed word that have been left out.
        sb.append(s.substring(i+1, (i+1+passedChars)));

        //return reversedString;
        return sb.toString();
    }

My reasoning for this being an O(N^2) algorithm:-

1. The loop = O(n)
2. StringBuilder.append = O(1)
3. Substring method = O(n) [as of Java 7]

On that note, if anyone else has a better solution than this, please feel free to share it! :)

I was aiming for a one-pass solution and therefore, opted out of splitting the string before the loop.

Appreciate the help!

EDIT: I meant to ask about the time complexity of the portion of the code that contains the loop. I apologize in advance if the question was misleading/confusing. The whole chunk of code is meant for clarification purposes. :)

Answer 1

Time complexity is O(n).

Each insertion (append(x)) to a StringBuilder is done in O(|x|), where |x| is the size of the input string you are appending. (independent of the state of the builder, on average).

Your algorithm iterates the entire string, and use String#substring() for each word in it. Since the words do not overlap, it means you do a substring() for each word one time, and append it to the builder (also once) - giving you 2|x| for each word x.

Summing it up, gives you

T(S) = |S| + sum{2|x| for each word x}

But since sum{|x| for each word x} <= |S|, this gives you total of:

T(S) = |S| + 2sum{|x| for each word x} = |S| + 2|S| = 3|S|

Since |S| is the size of the input (n), this is O(n)

---

Note that the important part is in jdk7, the substring() method is linear in the size of the output string, not the original one (you copy only the relevant part, not all of the string).

Answer 2

Here is an alternative solution which I believe may perform a little better.

public String reverseWords(String s) {
    String[] array = s.split(" ");
    int len = array.length;

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++) {
        sb.append(" ").append(array[len - i - 1]);
    }

    return sb.toString().trim();
}

Answer 3

Amit has already given you detailed explanation on the complexity computation, I would like to give you a simpler version.

In general, if we have nested loops, we consider the complexity to be O(N^2). But this is not the case always, as you have to do some activity n times for each nth part of input. E.g., if you have input of size 3, you have to do some action 3 times on each of the element. Then, you can say that your algorithm has O(n^2) complexity.

Since you are traversing and processing each part of your input string only once (even though you are using nested loops), complexity should be on the order of O(n). For proof, Amit has done quite a job.

Although, I would have used below code to reverse the order of words

String delim = " ";
String [] words = s.split(delim);
int wordCount = words.length; 

for(int i = 0; i < wordCount / 2; i++) {
    String temp = words[i];
    words[i] = words[wordCount - i - 1];
    words[wordCount - i - 1] = temp;
}

String result = Arrays.toString(words).replace(", ", delim).replaceAll("[\\[\\]]", "");