What is the time complexity of this "reverse words" algorithm? I had to write an algorithm that, given the input ['h', 'a', 'r', 'd', ' ', 'i', 's', ' ', 'c', 's'] would return ['c', 's', ' ', 'i', 's', ' ', 'h', 'a', 'r', 'd']. I found an algorithm that I think I am happy with, but unfortunately, I do not know how to compute its running-time.

The algorithm essentially has two stages. First, I reverse the entire string. Then, I scan that string to find words, and when I find a word, I reverse only that word. In terms of message, the first time we reverse we will do (n/2) steps. Then, for each word we find, we'll do (m / 2) steps, where m is the length of the word (m is not constant). How do I express the Big O notation for this? 

function reverseWords(message) {
  // reverse entire string
  reverseStrArr(message, 0, message.length - 1);

  let wordStart = 0;
  let wordEnd = null;

  for (let i = 0; i &lt; message.length; i++) {
    const char = message[i];

    if (char === " ") {
      wordEnd = i - 1;

      reverseStrArr(message, wordStart, wordEnd);

      // reset
      wordStart = wordEnd + 2;
      wordEnd = null;
    }

    if (i === message.length - 1) {
      reverseStrArr(message, wordStart, i);
    }
  }
}

function reverseStrArr(stArr, minIdx, maxIdx) {
  const midIdx = Math.floor((minIdx + maxIdx) / 2);

  for (let i = minIdx; i &lt;= midIdx; i++) {
    const tailIdx = maxIdx - (i - minIdx);

    const temp = stArr[tailIdx];
    stArr[tailIdx] = stArr[i];
    stArr[i] = temp;
  }
}
```
This algorithm runs in linear time in the size of the input $O(n)$.

To see why try to count how many times you read/write to a position in the string. Note that asymptotically this is equal to the total running time.