Question 4 (10 marks] The recursive algorithm Fib, shown in Figure 1, takes as input an integer n > 0 and returns the n - th Fibonacci number for Algorithm FiB(n): if n = 0 or n=1 then f = n else f = FiB(n-1) + FiB(n-2) endif; return f Figure 1: Fibonacci Algorithm. 1 Let an be the number of additions made by algorithm Fib(n), i.e., the total number of times the +-function in the else-case is called. Prove that for all n > 0, 2n = fu+1 -1. The algorithm is not efficient in terms of the total number of operations carried out. Without you having to give the actual such number, can you pin-point exactly where the inefficiency results from? Question 5 (10 marks) Let n 2 be an integer and consider a sequence 81, 82, ..., Sr of n pairwise distinct numbers. The following algorithm, shown in Figure 2 computes the smallest and largest elements in this sequence: (1) Algorithm MIN MAX(51, 52, ... ,8n): min = 811 mar = 81; for i = 2 ton do if 84 max (2) then mar = 8 endif endwhile; return (min, max) Figure 2: MinMax Algorithm. This algorithm makes comparisons between input elements in lines (1) and (2). Determine the total number of comparisons as a function of n