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)?
JavaScript
x
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