in Algorithms retagged by
1,035 views
0 votes
0 votes
What is the time complexity of calculating power of an element using DAC?
in Algorithms retagged by
1.0k views

4 Comments

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

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

for correct output,

return x*temp*temp; 

replaced by

 return x*temp;

moreover, it doesn't optimize the code. 

0
0

2 Answers

1 vote
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) = 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

selected by
0 votes
0 votes

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

 

 

Related questions

2 votes
2 votes
1 answer
3