Time complexity of isRotation algorithm

Question

This common code is said to run in O(N) time assuming isSubstring runs in O(N+M) time. How do we get O(N) time complexity from this?

    public static boolean isRotation(String s1, String s2) {
        int len = s1.length();
        if (len == s2.length() && len > 0) { 
            String s1s1 = s1 + s1;
            return isSubstring(s1s1, s2);
        }
        return false;
    }

user_16462842 · Answer

Usually when we say linear it means that with really really big number of basic operations our algorithm still performs in O(n). According to time complexity calculation of sublinear function like O(n+m) complexity gets pretty randomized but behaves like linear with large N. So generally we can say O(n)~O(n+m).

Time complexity of isRotation algorithm

1 Answers