@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?

Dark Mode

1,035 views

0 votes

0

1 vote

Best answer

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) = Log_{2}N.

eg. 2^{16} = ( 2^{8} )^{2} = ( ( 2^{4})^{2} )^{2} = ( ( ( 2^{2 })^{2 })^{2} )^{2 }= ( ( ( ( 2^{1 })^{2 })^{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 a^{n} get's dived into a^{n/2 }and a^{n/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(Log_{2}N).

Using recurrence relation I can say -

T(n) = { 1 if n=1

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

}

Using masters theorem -> a = b^{k }i.e. 1 = 2^{0} -> 1 = 1 and p = 0

**Therefore, T(n) = n ^{logba}Log^{p+1}N = n^{0}Log_{2}N = Log_{2}N**

Hence time complexity = O(Log_{2}N)