4 Consider the following two different algorithms to raise a

4. Consider the following two different algorithms to raise an integer x to a power of n (40 points) long pow2 (long x, int n) long powl (long x int n) if n 0) if n 0) return 1; return 1; if n 1) return X; result 1; if isEven n for (i 0; i

Solution

1. The first algorithm takes n steps, for loop Runs for n time . Hence the complexity of First Algorithm is O(n)
2. The pow2 function uses Divide and conquer approach and runs for O(log n ) time . Thats because It divides the problem into subproblems and soleves tem recursively at max the algorithm runs log n time .

For example:-

Suppose we have to calculate 2⁴ = 16
Algorithm 1 : 2 * 2* 2* 2 = 16. [Runs 4 times multiples each time by 2 so O(n) ]
Algorithm 2 : First calculates 2 * 2 = 4 , Now we already have 2² multiply with itself to calculate 2⁴ [Runs 2 times [2*2] and [2²*2²] so O(log n) ]



b) Obviously the second algorith is better because its running time is O(log n) and it runs faster than first algorithm that takes O(n)