в режиме реального времени сложность перестановки DFS решение

Question

https://leetcode.com/problems/permutations/ общее решение - рекурсия DFS

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0)
            return res;

        DFS(0, nums, res);

        return res;
    }

    private void DFS(int index, int[] nums, List<List<Integer>> res) {
        if (index == nums.length) {
            **//covert nums to list and add to res** o(n)
            return;
        }

        for (int i = index; i < nums.length; i++) {
            swap(nums, index, i);
            DFS(index + 1, nums, res);
            swap(nums, index, i);
        }
    }

    private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

из математики мы видим, что всего n! различные перестановки, и многие люди говорят, что o (n!) - сложность времени

, однако из кода мы можем видеть, что рекуррентность равна T (n) = O (n) (для добавления в перестановку) + T (n- 1) + T (n-2) + ... + T (2) + T (1), и я думаю, что O (n!) Игнорирует O (n) для добавления к перестановке. Я не знаю, как обобщить большое О, от этого повторения, кто-нибудь может помочь.

Большое спасибо