Recursion time complexity

Question

I am looking for help in understanding what the Time/Space complexity of my solution, for finding permutations of an array, is. I know that because I am using an Array.forEach method that my time complexity includes O(n), however since I am also using recursion I do not know how the time complexity changes. The recursion seems to me to be in O(n) time complexity as well. Does that make the overall time complexity of the algorithm O(n^2)? And for space complexity is that 0(n) as well? since each recursion call returns a bigger memory array? Thanks in advance.

  function getPermutations(array) {
      if (array.length <= 1){
        return array.length === 0 ? array : [array];
      }
      
      let lastNum = array[array.length - 1]
      let arrayWithoutLastNum = array.slice(0, array.length - 1); 
      let permutations = getPermutations(arrayWithoutLastNum);
    
      let memory = []
      permutations.forEach(element => {
        for(let i = 0; i <= element.length; i++){
          let elementCopy = element.slice(0);
          elementCopy.splice(i, 0, lastNum)
          memory.push(elementCopy)
        }
      })
    
      return memory
    }

You can write some timing code to get a first guess at this. But there is something fundamental that will give you a minimum in both time and space: the output. There are `n!` permutations of `n` items. So any algorithm that finds these permutations will be at least factorial. — Scott Sauyet, Sep 28 '22 at 12:59
You might find this answer useful [https://stackoverflow.com/a/13467808/9917714](https://stackoverflow.com/a/13467808/9917714) — Aleksa Majkic, Sep 29 '22 at 16:52

Recursion time complexity

0 Answers0