Big O using a stack is it O(1)?

Question

I trying to solve some algorithms problems. I have this one:

Write a method reverseWords() that takes a message as an array of characters and reverses the order of the words in place.

For example:

char[] message = { 'c', 'a', 'k', 'e', ' ',
            'p', 'o', 'u', 'n', 'd', ' ',
            's', 't', 'e', 'a', 'l' };

As a result we should get:

steal pound cake

The suggested implementation was this one:

public static void reverseWords(char[] message) {

    // first we reverse all the characters in the entire message array
    // this gives us the right word order
    // but with each word backward
    reverseCharacters(message, 0, message.length - 1);

    // now we'll make the words forward again
    // by reversing each word's characters

    // we hold the index of the *start* of the current word
    // as we look for the *end* of the current word
    int currentWordStartIndex = 0;
    for (int i = 0; i <= message.length; i++) {

        // found the end of the current word!
        if (i == message.length || message[i] == ' ') {

            // if we haven't exhausted the array, our
            // next word's start is one character ahead
            reverseCharacters(message, currentWordStartIndex, i - 1);
            currentWordStartIndex = i + 1;
        }
    }
}

private static void reverseCharacters(char[] message, int leftIndex, int rightIndex) {

    // walk towards the middle, from both sides
    while (leftIndex < rightIndex) {

        // swap the left char and right char
        char temp = message[leftIndex];
        message[leftIndex] = message[rightIndex];
        message[rightIndex] = temp;
        leftIndex++;
        rightIndex--;
    }
}

As you can see it goes over the array twice, N + N so it would be O(n)

but I think of using a stack would be a better approach, something like this:

public static void reverseWords(char[] message) {
        Stack<String> stack = new Stack<>();
        String word = "";

        int i = 0;
        while (i < message.length) {
            if (message[i] != ' ') {
                word = word + message[i];
            }
            else {
                stack.push(word);
                word = "";
            }
            i++;
        }

        stack.push(word);

        int j = 0;
        while (!stack.isEmpty()) {
            String wordStack = "";
            wordStack = stack.pop();
            for (i = 0; i < wordStack.length(); i++) {
                message[j] = wordStack.charAt(i);
                j++;
            }
            if (stack.size() > 0) {
                message[j] = ' ';
                j++;
            }
        }

In this case it goes over the array only one and insert and remove items from the stack and it is supposed to be O(1). I mean it would be also O(n) but the difference is that you go over the array only once.

What do you think? Am I right or not?

Thanks

Answer 1

You can't solve this task in O(1).

In order to reverse the words in the message (array of characters), you obviously need to go through the whole array at least once, and probably more than once, as we can see in the various solutions.

But you definitely cannot reverse all the words without actually reading the complete array to the end. Reading the array to the end is an O(n) operation, by definition, with n being the length of the array.

An operation is O(1) when the runtime (or the number of steps required) is constant, or at least does not depend on the length of the input. A method that reads its whole input cannot be O(1) with regard to the length of the input.

Note that the "with regard to..." part is very important - it does matter what the n means in an O(n).

For example, searching for an element in a hash table (or HashMap, in Java terms) is generally regarded to be a O(1) operation, because it does not depend on the number of elements already in the map. It does however very much depend on the length of the element to be searched - it needs to compute the hash value of this element, which requires going through the whole length of the element, so this is obviously an O(n) operation with regard to the length of the input. However, since the length of the element itself is usually negligible compared to the potential size of the whole hashmap, this O(n) is irrelevant. And since searching in the hash map is indeed independent of the size of the map, the whole thing is regarded as O(1).

Also note that O(1) does not mean that the algorithm will be fast for every given input. It only means that the runtime is constant, not that it is low. Usually O(1) algorithms have high fixed costs and high constant factors which is acceptable for large inputs, but for small inputs an O(n) algorithm with a low fixed overhead may well be faster.

Taking the hash map example, if there are 5 elements in the map, and you want to check if the map contains a given value, it is much, much faster to go through all 5 elements, instead of using the generic algorithm - calculating the hash of the searched element and using it to predict where it should be stored in the map. This is also true with 10 or 50 elements in the map, but with 5 million, it's a different story, and with 5 billion it's a much different story.

Answer 2

The first solution is should be faster, but they both in O(n).