Help calculating big (O) - string permutations

1

Hi all, I wrote some code to generate all permutations of a string. I am trying to determine the big (O) of my code.

I took at look at some solutions online and they took a different approach than I did.

Here is my code

const insert_at_each_index = (letter, perms) => {
  const ans = [];

  for (let i = 0; i < perms.length; i++) {
    const perm = perms[i];
    let j = 0;

    for (let j = 0; j <= perm.length; j++) {
      const first_chunk = perm.substring(0, j);
      const last_chunk = perm.substring(j);
      ans.push(`${first_chunk}${letter}${last_chunk}`);
    }
  }

  return ans;
};

const perms = (s) => {
  if (s.length === 1) {
    return [s];
  }
  const first = s[0];
  const rest = s.substring(1);

  const rest_perms = perms(rest);

  const ans = insert_at_each_index(first, rest_perms);
  return ans;
};

Basically my approach was a recursive one:

  1. for a given string split the string into first letter and rest of the letters
  2. calculate all the permutations for the rest of the letters
  3. insert the first letter at every position possible in every permutation of the rest of the letters
  4. the result is all possible permutations of the given string

I have no idea how to determine the time complexity of this. And it looks like my approach was different than most of the solutions online. Can anyone help me out?

Thanks!

2

Check a handy textbook or web search. This seems to be a decent summary. It’s not much different than finding a dominant term in a function in mathematics.

You’ll have to inspect your algorithm for the actual estimate as it involves determining the complexity of each step. Permutations grow factorially so I would assume (with some little evidence) that a naive implementation would be O(n!).

3

Yep - I know that the standard implementation is at least n! but I have no idea if my function is slower than that. It is implemented in different way than most of the example that I’ve seen online

4

Let me rephrase. You’re generating all permutations and permutations are O(n!). That means your algorithm is O(n!) or worse. You’ll have to do the line-by-line to calculate it exactly, but I don’t think you can get appreciably worse.

5

Right - I’m trying to break understand the Big (O) of my particular algorithm. I know I have to break it down line by line to come up with a solution. I know that the best case run time is O(n!).

My problem is I do not know how to break this particular algorithm down line by line and determine the worst case run time. That’s what I am asking for help on

6

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.