0

this is a famous problem, but I have just started to study time and space complexity. This is my implementation and i like to know if I'm right or not.

 public static void main (String[]args){
    String s1 = "Ciao";
    String s2 = "ciAo";
    String s3 = "Fratfem";

    if (s1.length() == s2.length()){
        if(permutation(s1,s2))
            System.out.println("Correct");
    }
    else{
        System.out.println("Not same length");
    }
}


public static boolean permutation(String s1, String s2){
    String s = s1.toLowerCase(Locale.ROOT) + s2.toLowerCase(Locale.ROOT);
    Set<Character>set = new HashSet<>();
    for (Character c: s.toCharArray()){
        set.add(c);
    }

    if (set.size() == s1.length())
        return true;
    return false;
}

Convention : s1.length + s2.length = n

  • Worst Case Space Complexity: I think it's equal to O(n*2).

  • Worst Case Time Complexity: O(n) because we have to add all, and check, all characters.

I'd like to know if i am wrong, thanks.

Improve this question
2
  • please, describe the problem that you tried to solve with this code Commented Jun 15, 2021 at 15:41
  • I think the algorithm doesn't check out. If a word has a repeating letter, it will never be able to be considered a permutation of another word. For example feet and fete Commented Jun 15, 2021 at 15:43

1 Answer 1

Reset to default
1

You're wrong in just about every way.

Your algorithm is flat out broken.

For example, "CIIO" and "IICO" are not considered equal, even though one is clearly a permutation of the other. Your algorithm prints nothing if the strings are of equal length but not a permutation (which is weird output).

This algorithm does not have the time/space complexities you mentioned.

Where are you getting O(n^2) from?

The main method doesn't do any looping at all, other than invoking permutation once, so we don't need to look at it.

permutation will first craft a new string by concatenating the 2 input strings; this takes n time and n space (s1 and s2 can't be collected nor can s, they're all in memory as long as permutation is running). You then loop over each character in it, which is also O(n). You then invoke size and length, both O(1) (i.e. ignorable) operations.

So, you have O(n), and then O(n), which is just O(n). (Because it's O(2n), and O(n) means: "If you feed this algorithm data that is incrementally more complicated, as defined by 'having incrementally higher n', and you graph 'n' against 'time/space taken', then eventually, at some unknown point, the graph starts looking like the graph y = x does.

y = 2x looks just like y = x, hence why saying something is O(2n) is useless and therefore not correct. That just becomes O(n). Same reason O(2n^2 + 1000n) is just O(n^2). Because y = 2x^2 + 1000n, eventually, looks exactly like y = x^2 does.

How would one write the correct algorithm?

Depends on what you mean by permutation. Presumably, if shuffling letters around for one of the strings lets you make the second, i.e. ciio and iico are permutation-wise equal, but ccio and ciio are not, nor are cio and ccio.

In that case:

  • Turn s1 into a char array. (O(n)).
  • Sort this char array using Arrays.sort, which is O(n logn) - but you'd have to know that this is the performance characteristic of sort.
  • Do the same to s2. (O(n) + O(n logn)).
  • Check that the 2 arrays are equal. (O(n)).

That sums up to 2 O(n logn) and a whole bunch of O(n), which just becomes O(n logn). It becomes quite easy to 'add them up', you're just looking for the most significant factor; any factors of lesser significance are irrelevant, as are constant repeats of the most complex fcator.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.