1
$\begingroup$

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 < 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 <= midIdx; i++) {
    const tailIdx = maxIdx - (i - minIdx);

    const temp = stArr[tailIdx];
    stArr[tailIdx] = stArr[i];
    stArr[i] = temp;
  }
}
```
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Reversing the string certainly O(n). We traverse 1/2 the string, but at each traversal, we do two operations. But then we have to traverse the string again in order to reverse the "words" in the string. Intuitively I know that that is O(n) operation as well, and we don't care about constants in Big O notation, but I can't seem to articulate why that intuition should be correct. I could argue that the maximum number of words in an input of size n is n / 2 - e.g. ['a', ' ', 'i', ' ', 'a']; $\endgroup$ – Steven L. Jan 24 at 20:19
  • $\begingroup$ You can formulize your intuition using amortized complexity. Divide algorithm into phases, where each phase starts at the end of a call of reverseStrArr and ended at the end of the following call. Note that the time spent in each phase inside the function can be bounded by a constant factor in the time spent outside the function, hence by "forgetting" and giving a constant additional weight to each iteration of the "i" loop you get an upper-bound on the running time $\endgroup$ – narek Bojikian Jan 24 at 22:59
0
$\begingroup$

Have you run the code?

If you reverse the array ['d', 'r', 'a', 'h', ' ', 's', 'i', ' ', 's', 'c'] you get the desired result of ['c', 's', ' ', 'i', 's', ' ', 'h', 'a', 'r', 'd']. If you then reverse the words you get ['s', 'c', ' ', 's', 'i', ' ', 'd', 'r', 'a', 'h'], which is not what you want.

You can't get better than an $O(n)$ complexity for reversing an array of size $n$. If you want an explanation as to why this is the case, then we must be slightly more precise. Below I do the analysis for an easy to analyze implementation, not an inplace version. (The analysis is similar for an inplace version, and I think that you can work it out.)

Let's assume that the operations which have a cost are "reading a value from an array", "writing a value to an array", and "comparing two values". The input to our algorithm is an array input of size $n$ and the output is an array output also of size $n$, and we must ensure that when the algorithm terminates that output[i] == input[n-i-1] where $0 \leq i \leq n$. (Take a minute and convince yourself that this is a correct description of the problem, and that the equality is correct for both even and odd values of $n$.) To make the analysis as simple as possible, we will assume that there is an array named output of size $n$ just waiting for us, and that output[i] == 0 for all $i < n$.

Therefore, any algorithm must assign to output[i] the value input[n-i-1] for all $n$ possible values of $i$, unless input[n-i-1] == 0, in which case no assignment needs to be made, as the correct value is already present. So one possible implementation would loop through the $n$ different values of $i$ and check if input[n-i-1] == 0 and continue when the condition was true and assign the value to output[i] when the condition was false.

If the input array is $n$ 0s then this implementation would perform exactly $2n$ operations, one operation to get the value at input[n-i-1] and one operation to compare it to 0. However, if there are no values of 0 in the input, then there are exactly $3n$ operations performed, $2n$ of the operations are the same as before, but now there are $n$ assignments of the value to the correct position in the output array (here we assume we don't need to read the value from the input array again). More generally if 0 occurs $m$ times in the input then there are exactly $2n + m$ operations performed.

Now this part is important: if we don't check the value, but instead just do the assignment then there are always $2n$ operations, one to read from the input and one to write to the output. Checking the value each time to avoid an unnecessary copy does more work than not checking the value in the majority of cases. Since any algorithm which uses these operations must do at least this much work, you can't do better than $O(n)$ operations.

But what about other operations? For an inplace version you might consider an operation which swaps two values in the array swap(i, j). Such an operation allows you to reverse the array in $n/2$ operations (for even $n$), which is still $O(n)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you - I have updated my input. It was the wrong one. Your comment gives me the answer, but not the reason why. (Not meant that to be snide in any way - just trying to communicate that I don't understand the why). $\endgroup$ – Steven L. Jan 24 at 20:17
  • $\begingroup$ After your comment I updated my comment with an analysis, but I think you then changed the question. In anycase, it's easy to see that as the number of words goes up that the number of swaps you need to do goes down. If all the words are of length 1 then you need to do no swaps, and if there is 1 word then you just reverse the array again. You can do an induction on the number of words to prove a complexity of $O(n)$. $\endgroup$ – Jack Jan 24 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.