CODEWITHSUNDEEP
javaalgorithmbig-o
PAujla
PAujla

Reputation: 155

Does this algorithm have time complexity of 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, it seems this would have time complexity of O(n) and space complexity of O(1). This is also suggested by the author. However, function reverseWords first calls reverseCharacters which has a time complexity of O(n) and space complexity of O(1).

Then the for loop which will run max of n times and it calls reverseCharacters again which contains a while loop which would also run n times. Doesn't this mean together the time complexity will be O(n^2)?

Had the code from the helper function actually been implmented into the reverseWord function does it change the space or time complexity?

Upvotes: 3

Views: 89

Answers (1)

Thiyagu
Thiyagu

Reputation: 17920

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

True

[..]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 string. The bounds leftIndex and rightIndex point to the start and end of a word and does not iterate through the whole string.

Thus, each character in the string is seen twice which is like O(n + n) which is O(n).

Example:

For the string abcd efg hijk, it is evident that reverseWords scans this string.

When it sees a space or the end of string, it calls reverseCharacters. This happens three times for the above string - from (a - d), (e - g), and (h - k). It reverses the characters between the bounds. Each of these operation is not O(n).

Upvotes: 3

Related Questions