algorithm - Is this method BigO(n^2) or BigO(nLog(n))?

Question

This is a method i wrote that checks if two strings are premutations of each other:

public static boolean permutation(String str1, String str2) {

boolean terminate = false;

for(int x = 0; x < str1.length(); x++){
    for(int y = 0; y < str2.length(); y++){
        if(y != str2.length() - 1){
            if(str1.charAt(x) == str2.charAt(y)){
                str1.replace(String.valueOf(str1.charAt(x)), "");
                str2.replace(String.valueOf(str2.charAt(y)), "");
                break;
            }
            
        }else{
            if(str1.charAt(x) != str2.charAt(y)){
                return false;
            }else{
                str1.replace(String.valueOf(str1.charAt(x)), "");
                str2.replace(String.valueOf(str2.charAt(y)), "");
            }
            
        }
        
    }
    
}

return true;

}

as you see in the code I'm using a for loop inside another for loop but not checking all the elements of x with y (but sometimes checking all the elements of y with the current value of x), So I'm guessing is BigO(nLog(n)) since we are not comparing all the elements overall but my mind is telling me this might be BigO(n^2). Also I am removing the indexes once a certain condition is met so the other remained indexes Won't inspect the removing elements, in my opinion it is a BigO(nLog(n)) but just in case it is not i want to know why.

Answer 1

You haven't considered the time complexity for the replace() method. It takes O(N) time complexity.

Agreed that you are processing the strings depending upon certain conditions, but the 2 for loops anyway make the time complexity O(N^2).

Therefore, overall time complexity = O(N^2 * N) = O(N^3).

To be precise, if the length of str1 is N and the length of str2 is M, then the time complexity ~ O (N * M * (N + M)).