1,035 views
What is the time complexity of calculating power of an element using DAC?

@MiniPanda

See this code

int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y-1);
return x*temp*temp;
} 

here I have modified the optimized code,

is it correct?

Try passing power(3,4) ..I guess you will get 3^15 ..

for correct output,

return x*temp*temp;

replaced by

return x*temp;

moreover, it doesn't optimize the code.

Algorithm without using divide and conquer: O(n)

- run for loop for n time where n is the power and multiply number with itself in every iteration result.

Algorithm with using divide and conquer: T(n) = Log2N.

eg. 216 = ( 28 )2 = ( ( 24)2 )2 = ( ( ( 22 )2 )2 )= ( ( ( ( 21 )2 )2 )2 )

This is how we divide the given problem into subproblem each of size n/2.

So rather than running for loop for 16 time I can run it for 4 times and with some constant amount of time for multiplication I can get result.

so an get's dived into an/2  and an/2 .

Power(a,n)
{
if(n==1)
return a;
else
{
mid=n/2;
f=Power(a,n/2);
f=f*f;
return f;
}
}

Here you are recursively calling Power(a,n/2) [ problem is getting divided into n/2 ] and doing some constant work c involving calculation of mid and checking conditions. Also multiplication will take some constant time.

I can say directly, problem is getting divided into half size every time, its complexity is O(Log2N).

Using recurrence relation I can say -

T(n)  = {    1 if n=1

T(n/2) +c if n>1

}

Using masters theorem -> a = bi.e.  1 = 20 -> 1 = 1  and p = 0

Therefore, T(n) = nlogbaLogp+1N = n0Log2N = Log2N

Hence time complexity = O(Log2N)

http://data.conferenceworld.in/ICSTM2/P904-912.pdf

T(n) = aT(n/b)  + f(n)

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

T(n) = T(n/2) + C

Now,

g(n) = nlog (a) base(b)

nlog (1) base(2)

n^0 = C

AS g(n) = f(n)

then,

time complexity = O(log n)  ANS