All algorithms in the question need a proof of runtime and a proof of correctness

Question 3. (10 points) Recursive permutations For every positive integer n, there are n! permutations of 11,2,--. , n}. There is an ordering on the permutations defined by the lexicographic (dictionary) order on lists, e.g. for n = 3 we have the following ordering of the permutations: 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3, 2,1 HW 1 1. (5 points) Give a recursive algorithm which takes two positive integers n and k E {1, 2, . . . , n!), 'n) in 0(m2). Eg. for-3, k-4 the which then returns the kth permutation of {1, 2, algorithm should output Hint 3.1. Try to find the first number in the permutation, by counting the the position of the permutation in the lexicographic ordering of all permutations in O(n2). 2,3,1 2. (5 points) Give a recursive algorithm which takes a permutation of { 1, 2, , n} and returns E.g. for the input (3, 1,2), the algorithm should output 5