Performance Measurement

There are at least two different algorithms that can compute XN for some positive integer N. Algorithm 1 is to use N – 1 multiplications. Algorithm 2 works in the following way: if N is even, XN = XN / 2  XN / 2; and if N is odd, XN = X(N – 1) / 2  X(N – 1) / 2  X. Figure 2.11 in your textbook gives the recursive version of this algorithm. Your tasks are: (1) Implement Algorithm 1 and an iterative version of Algorithm 2; (2) Analyze the complexities of the two algorithms; (3) Measure and compare the performances of Algorithm 1 and the iterative and recursive implementations of Algorithm 2 for X=1.0001 and N = 1000, 5000, 10000, 20000, 40000, 60000, 80000, 100000.