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

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).