The power function f(a, b) can be defined recursively 1 if b=0 f(a,b) = a.f(a, (b − 1)/2)2 if b>0 is odd f(a, b/2)2 if b>0 is even Recalls the recursive function, algorithm for power calculation of above function and compute the time complexity of the above power function Consider the given function: 1 if b = 0 f(a,b) = a.f(a, (b − 1)/2)2 if b>0 is odd f(a, b/2)2 if b > 0 is even) (1) Consider the case of b>0 and “b” is even ,in that case we all f(a,b/2),since the b/2 is even when bis even will also give the even number so at each recursive call the b is halved. (2)Consider the case of b>0 and b us odd ,in that case we all f(a,(6-1)/2),since the (6-1)/2 is even when b is odd will also give the even number, so at each recursive call the bis halved. 1 (3)At each recursive call we call b/2 until we reach b=0 so the time complxity is oſb log2 b) here either we are calling iſ a,(6-1)/2) or f(a, b/2) thus recurrence relation is T(n) = T(n/2)+theta (k) so solving it we get n, n/2,n/4…1 so total terms are logn so total work = k+k+k+k….logn times = k*logn O(logn)

55 0

Get full Expert solution in seconds

$1.97 ONLY

EXPERT ANSWER

At each recursive call, we perform a recursion and some operation for current call. We can represent the recurrence as

T(n) = 2T(n/2) + O(1)

= 2(2T(n/4)+O(1)) + O(1)

= 2(2(2T(n/8)+O(1))+O(1)) + O(1)

.

.

.

= 2kT(n/2k) + k.O(1)

For base case,

n/2k = 1

n = 2k

k = log2n

Thus, the time complexity comes to be O(log n)