0

I am reading "Cracking The Coding Interview", and came upon a question that asks to write an algorithm that checks to see if one string is a permutation of another. The book's solution doesn't explain the time complexity(go figure), so I was wondering what it would actually be for the function below.

function permutations(a, b) {
  if (a.length !== b.length) {
    return false;
  }

  const aSorted = a
    .split("")
    .sort((a, b) => a.localeCompare(b))
    .join("");

  const bSorted = b
    .split("")
    .sort((a, b) => a.localeCompare(b))
    .join("");

  return aSorted === bSorted;
}

The split and join functions must be O(n), and I believe the built in sort function is O(n log n) (which I don't even understand). Since O(n log n) is worse than O(n), do we just forget about the other operations?

Dan Zuzevich
  • 3,651
  • 3
  • 26
  • 39
  • Yes, that's right. – TYeung Sep 01 '21 at 15:33
  • 1
    Does this answer your question? [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – TYeung Sep 01 '21 at 15:35
  • Comparing two strings for equality is also most likely O(n). Thus 2 * (O(n) + O(n log n) + O(n)) + O(n) = O(n log n) – Jonas Wilms Sep 01 '21 at 15:38
  • This problem can be easily solved in O(n). I am continually puzzled by bad solutions like this and why books (and sites) that promote them are so popular. – RBarryYoung Sep 01 '21 at 17:50
  • 1
    @RBarryYoung: clearly it can, but this was described as a coding interview question. You describe this solution and say, "Of course with the `sort`, that's `n log n`. Should we try to improve it, or is that enough for now?" I'd much rather interview a coder who came up with a working solution and noted its potential performance flaws than one who struggles overlong to find a more optimized solution but never manages to get there. – Scott Sauyet Sep 01 '21 at 18:10

0 Answers0