Q1. Consider the problem of generating all the possible permutations of length n. For example, the permutations of length 3 are: {1,2,3}, {2,1,3},{2,3,1}, {1,3,2}, {3,1,2}, {3,2,1}. In this question, you will provide:

a)Well documented pseudocode of a recursive algorithm that computes all the permutations of size n. Calculate the time complexity of your algorithm using the big-Oh notation. Show all calculations.

b)Well documented pseudocode of a non-recursivealgorithm that computes all the permutations of size n. The only data structure allowed is a stack (you may use maximum up to two stacks). Any other memory usage should be O(1). Calculate the time complexity of your algorithm using the big-Oh notation. Show all calculations