Problem figuring out time and space complexity?

Question

The question was to check whether two strings are rotation of each other or not. So, here is the function I wrote for the same:

 bool areRotations(string s1, string s2)
        {
            int n1 = s1.length(), n2 = s2.length();
            if (n1 != n2) return 0;
            s1 += s1;
            if (s1.find(s2) != string::npos)
                return 1;
            else
                return 0;
        }

I just checked whether s2 is present in s1+s1, if it is there, then s1 and s2 must be rotation of each other.

I am not able to figure out the time and space complexity of my code. What I can understand is that it should be O(n) time complexity because first to concatenate s1 to s1, we have to create a copy of s1, and also to find s2 in s1, we have to traverse, hence making time complexity O(n). For space also, it should be O(n), because we are making a copy of s1. Is this correct?

Answer 1

I am not able to figure out the time and space complexity of my code. [...] Is this correct?

std::string::length runs in constant time (since C++11). The comparison and the concatenation run in linear time. But the overall algorithm could run in a non-linear time.

Indeed, the C++ standard does not actually require any specific algorithm or guarantee a complexity for std::string::find. Consequently, it is not possible to give an answers independent of the STL implementation you use. If the implementation is naive or use a famous Boyer-Moore algorithm, the worst-case time-complexity is likely to be O(n^2) in your case (where n is the size of the input string). This could happen with inputs like s1="aaaaaaaaaca" and s2="aaaaaaaaaac". Despite std::search provide stronger guarantees, it does not provide any search algorithm running in linear-time. To ensure a linear-time complexity, you can use the KMP search algorithm (or better variants like the 2-way string-matching algorithm).

Thus, with the KMP algorithm, the complexity in time and space of your solution would be O(n). This is optimal as the input strings need to be read and stored somewhere (at least in your implementation).