Data Structures Exercise 1 1. Consider the following recursive algorithm for sorting a given array A. First, find the maximal and minimal elements in A. Swap the maximal element with the last element of A, and swap the minimal element with the first element of A. Call the algorithm recursively to sort A from the second element to the next to last element. (a) Write pseudocode for the algorithm. Don't forget to deal with the base case! (b) Write a recursive formula for the runtime. (c) Use induction to prove that the runtime is O(na). 2. For the following pairs of functions f,g:N + N, state if f(n) is 0,12 or of g(n). (a) f(n) = 2n2 n(2n 5), g(n) = n2. (b) f(n) = n, g(n) = 2". (c) f(n) = 10vn, g(n) = 2". (d) f(n) = 2", g(n) = 3". (e) f(n) = log2 (n), g(n) = log2 (na). 3. Let d be an integer, and let A be a sorted array of integers. Give an algorithm to check if A contains two numbers a, b that satisfy b- a = d. The runtime of the algorithm should be O(n). You may describe the algorithm in words or pseudocode