Consider the following two different algorithms to raise an

Consider the following two different algorithms to raise an integer x to a power of n: 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; for (i-0, i

Solution

Answer:

a) The first algorithm would run n times. Hence O (n) . It has only one for loop that runs from 0 to n.
b) But in the second one the size of the problem decreases by a factor of n/2. Hence it would be O (logn). The second one is more efficient because it takes O(logn) time only which is lesser than O(n).