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 )2 = ( ( ( ( 21 )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 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 = bk i.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