Algorithm help

(d) The two recursive algorithms presented below calculate the same expression 2" for a given non-negative integer n. Which algorithm is faster? Provide a brief explanation. [2 marks] ALGORITHM poweri (n) if n == o return 1 else return poweri (n-1) + poweri (n-1) ALGORITHM power2 (n) if n == o return i else return 2xpower2 (n-1) (e) A recursive algorithm h(n, k) is given below. ALGORITHM hin, k) //Input: two positive integers n and k. if k == 1 return n else if n == k return 1 else return h(n-1, k-1) + h(n-1,k) (i) Perform box-tracing of the algorithm and demonstrate how it computes h(5,3). Specify the value found. [6 marks] (ii) Explain whether the base case is appropriate or not. If you think that the algorithm will not terminate on some input values, give an example. Observe that only positive integers n and k can be considered as input parameters. [2 marks] (f) Suppose the number of elementary operations performed by an algorithm is n + 1000n logan -5n+ 5. Indicate the complexity class O(?). Use the formal definition of Big- to prove your statement. [3 marks]