Skip to content
Advertisement

What’s the time complexity of this anagram checker?

What is the time complexity of this method? I read that time complexity of contains() method of String is O(n) and I’m using it inside my loop that goes over the input string is the time complexity O(n2)?

public static boolean isAnagram(String str, String str1) {
    if(str.length() != str1.length()) {
        return false;
    }
    
    for(int i = 0; i < str.length(); i++) {
        String letter = String.valueOf(str.charAt(i));
        
        if(!str1.contains(letter)) {
            return false;
        }
        
        letter = String.valueOf(str1.charAt(i));
        if(!str.contains(letter)) {
            return false;
        }
    }
                
    return true;
}

Advertisement

Answer

Yup O(n^2) since there is n number of iteration for the for loop and each iteration call contains twice

User contributions licensed under: CC BY-SA
10 People found this is helpful
Advertisement