# Problem figuring out time and space complexity?

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?

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