Algorithmic complexity of string rotation

Question

I'm a little new to complexity, and was trying to determine the algorithmic complexity of the process below, which calculates whether a given string is a rotation of another given string (i.e., if "bcdea" is a rotation of "abcde"). I'm pretty sure this breaks down to O(n), as each check in the function breaks down to n at worst (I think!). Does that sound about right?

public class Rotate {
        public static void main(String[] args) {
            String str1 = "abcde";
            String str2 = "bcdea";
            System.out.println(isRotation(str1, str2));
        }
        
        public static boolean isRotation(String str1, String str2) {
          if(str1 == null || str2 == null){
            return false;
          }
          
          System.out.println(str1 + str2);
          if(str1.length() == str2.length() && (str1 + str2).indexOf(str2) > 0){
            return true;
          }
          
          return false;
        }
    }

Algorithmic complexty does not measure runtime.

user207421
– user207421

2021-03-03 23:05:05 +00:00
Commented Mar 3, 2021 at 23:05 — user207421
– user207421, Commented Mar 3, 2021 at 23:05
Gah, sorry, I meant algorithmic complexity, not runtime.

ZapRowsdower
– ZapRowsdower

2021-03-04 00:32:17 +00:00
Commented Mar 4, 2021 at 0:32 — ZapRowsdower
– ZapRowsdower, Commented Mar 4, 2021 at 0:32

Green Cloak Guy · Accepted Answer · 2021-03-03 23:06:11Z

2

The expression at issue is this one:

(str1 + str2).indexOf(str2)

Everything else in your method is obviously O(1), so whatever the complexity of this expression is is going to be the complexity of the method as a whole. Let's say that n1 represents the length of the str1 and n2 represents the length of str2, for our purposes.

Now, there are two parts here. String concatenation can generally be assumed to have O(n1 + n2) == O(n) runtime, as the component operations are (1) allocating space (constant), copying str1 (takes n1 time), and copying str2 (takes n2 time).

Meanwhile, Java's String.indexOf() has complexity O(m * n), where m is the length of the search string and n is the length of the pattern string. Here, that resolves to O((n1 + n2) * n) == O(n * n) == O(n^2).

So the complexity of the method as a whole would be closer to O(n^2) than to O(n). The complexity could be easily lowered by using a more efficient, lower-complexity implementation of indexOf(), as mentioned in the linked question.

If we look at algorithmic complexity, then the method is O(n), since indexOf() is the limiting element and there exist O(n) implementations of that. However, if we look at runtime complexity, taking this as an implementation rather than an algorithm, then the runtime would be O(n^2).

(sidenote: I think it should be (str1 + str1).indexOf(str2), not (str1 + str2).indexOf(str2). But that doesn't significantly change the complexity, and isn't the point of this answer)

answered Mar 3, 2021 at 23:06

Green Cloak Guy

24.8k4 gold badges39 silver badges58 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

ZapRowsdower Over a year ago

Fantastic insight, thank you very much. As was noted above, I misspoke and actually was just looking for the algorithmic complexity of the program, which it sounds like I was on the right path in my assumption. In a similar vein, would your answer hold true for the space complexity as well?

ZapRowsdower Over a year ago

Or, I should say, the algorithmic complexity is O(n^2) due to the concatentation in addition to the usage of indexOf()? In which case, delegating the concatenation to a separate action would reduce the entire function to O(n)? Assuming O(n) would be the space complexity as well?

Green Cloak Guy Over a year ago

@ZapRowsdower Don't forget, O-notation is a measure of complexity class - an algorithm with 2n operations has the same class as one that takes 20n operations (any fixed, constant number of ns - the runtime grows linearly as n increases). Accordingly, if you have multiple operations with the same complexity in sequence, they add together but the function remains in the same complexity class. In this case space complexity would be O(n) also - the only real space you're allocating is the space for the concatenation, which is exactly twice the size of the input.

Collectives™ on Stack Overflow

Algorithmic complexity of string rotation

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related