The computational complexity of generating permutations depends on the size of the input set. As the size of the set increases, the number of permutations grows exponentially. Generating permutations of large sets can become computationally expensive and may require optimization techniques such as pruning or efficient algorithms like Heap's algorithm.