Java – Is the time complexity of the algorithm O(n) or O(n^2)?

  public static void reverseWords(char[] message) {
    reverseCharacters(message, 0, message.length - 1);
    int currentWordStartIndex = 0;
    for (int i = 0; i <= message.length; i++) {
        if (i == message.length || message[i] == ' ') {
            reverseCharacters(message, currentWordStartIndex, i - 1);
            currentWordStartIndex = i + 1;
        }
    }
}

private static void reverseCharacters(char[] message, int leftIndex, int rightIndex) {
    while (leftIndex < rightIndex) {
        char temp = message[leftIndex];
        message[leftIndex] = message[rightIndex];
        message[rightIndex] = temp;
        leftIndex++;
        rightIndex--;
    }
}

At first glance, this seems to have the time complexity of O(n) and the spatial complexity of O(1). This is also what the author suggests. However, the function reverseWords first calls reverseCharacters with a time complexity of O(n) and a spatial complexity of O(1).

Then the for loop runs up to n times, and it calls reverseCharacters again with a while loop that will also run n times. Does this mean that the time complexity will be O(n^2)?

If the code in the helper function is actually implemented into the reverseWord function, does it change the spatial or temporal complexity?

[..] the for loop which will run max of n times

Correct

[..] and it calls reverseCharacters again which contains a while loop which would also run n times.

This is not true.

reverseCharacters is called when reverseWords encounters a space or the end of a string. The boundaries leftIndex and rightIndex point to the beginning and end of the word and do not traverse the entire string.

Therefore, each character in the string is seen twice, just like O(n + n) or O(n).

Example:

For the string abcd efg hijk, apparently reverseWords scanned this string.

When it sees a space or the end of a string, it calls reverseCharacters. For the above string, this happens three times – from (a - d), (e - g), and (h - k). It inverts characters between boundaries. Each of these operations is not O(n).