Java simple application Complexity

I had to resolve a problem for an interview, and i didn't understood something. The problem was, for a string like "we like hiking" to reverse the string like this: "ew ekil gnikih", this means, to explode the string like: str.split(" ") and then, each word to reverse and to add to the new string.

The problem was at the end of the problem, because was asking something about Complexity, like: " - expected worst-case time complexity is O(N)" - expected wors-case space complexity is O(N) (not counting the storage required for input arguments)

I resolved the problem like this:

public static String solution(String S){

    if(S.length()>1 && S.length()<200000){

        String toReturn = "";

        String[] splitted = null;
        if(S.contains(" ")){
            splitted = S.split(" ");
        }
        else{
            splitted = new String[]{S};
        }

        for(int i=0;i<=splitted.length-1;i++){
            String wordToChange = splitted[i];
            String reversedWord = "";
            for(int j=wordToChange.length()-1;j>=0;j--)
                reversedWord+=wordToChange.charAt(j);

            toReturn+=" " + reversedWord;

        }

        return toReturn.trim();

    }
    return null;
}

What i should do about the complexity request? Thanks!


ANSWERS:


I think this is not the correct answer for at least the time complexity.

In my opinion the splitting of a String will most likely be a complexity of O(n). And it'll just add to next complexity, therefore we can forget about it.

Now you're creating an empty String and concatenating a char on top of each String. Here you're assuming this operation is as cheap like inserting a value into an array (O(1)).

In this case you should assume, that you're creating a new String each time with the member method concat(). If you're have the chance of looking into the implementation of String.concat(String) you'll see that this method is creating another char[] in the length of string1.length + string2.length and is copying both string1 and string2 into it. So this method alone has a complexity of O(n).

Because you're concatenating n chars for one word of n length, it has the complexity of O(n * (n / 2)) = O(n^2) for one word. Assuming the worst case of just one word, you have the complexity class of O(n^2).

I would concur with the space complexity class of O(n) for your code. But this is just under the assumption of the intelligence of the JVM reusing you're unused space.

Your code should work, but I think it is really not good code for this problem. You can improve it with a StringBuilder or direct operations on a char[].

The StringBuilder is a good idea, because it acts similar to a Vector or a ArrayList. I has a much bigger char[] working in its background than a String. If it's capacity is exceeded (by using the append() method), it will create a much bigger array, something like 2 time the size of the previous backing array. This might only be a time complexity of O(nlogn). But you can tweak it furthermore by initializing the StringBuilder with a capacity of the same size as your initial String. This means the backing char[] will not be copied at all, because you'll not exceed it's capacity.

Here is an example with the use of a char[]:

private static void reverseCharArray(char[] result, int start, int end) {
    int halfDifference = (end - start) / 2;
    for (int i = 0; i < halfDifference; i++) {
        char buffer = result[start + i];
        result[start + i] = result[end - i - 1];
        result[end - i - 1] = buffer;
    }
}    

public static String reverseWordInString(String string) {
    char[] stringAsCharArray = string.toCharArray();

    int indexStart = 0;
    for (int indexEnd = 0; indexEnd < stringAsCharArray.length; indexEnd++) {
        if (stringAsCharArray[indexEnd] != ' ') {
            continue;
        }
        StringOperations.reverseCharArray(stringAsCharArray, indexStart, indexEnd);
        indexStart = indexEnd + 1;
    }
    StringOperations.reverseCharArray(stringAsCharArray, indexStart, stringAsCharArray.length);

    return String.valueOf(stringAsCharArray);
}

About time complexity:

Worst-case O(N) means that you should have a worst case scenario in which you compute N iteration in order to get the result, in your case you split the String into an array of Strings [operation that probably takes O(N), but it depends on the method split()], then for each String in the array you start from the end of the String and invert the characters. So your worst case is O(N) + O(N)... = O(N)

About space complexity:

Each String is an object and you reserve space in memory for each String you create, here you have an array of Strings, means that you create an object for each word or letter you split from the original string. You worst case is a string like "I a m t h e o n e" in which you create a String for each character -> O(N)

Hope this clarifies your doubts



 MORE:


 ? Are exponential algorithms (with very small exponents) faster than the general logarithmic algorithm?
 ? Simple algorithmic complexity of two nested loops
 ? Reducing the time complexity of the code below
 ? Number of steps in a nested loop
 ? Determine the computational complexity of the following algorithm
 ? Big O Time complexity for Find All Numbers Disappeared in an Array
 ? How to count the number of 1 bits set in 0, 1, 2, ..., n in O(n) time?
 ? Sorting time always different from first sort
 ? Run time complexity for Reversal of array?
 ? Python - time complexity O(N**2)