retagged by
1,683 views
0 votes
0 votes
What is the time complexity of calculating power of an element using DAC?
retagged by

2 Answers

Best answer
1 votes
1 votes

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

3 votes
3 votes
5 answers
1
ayushigupta asked Oct 11, 2016
2,995 views
Given 2 sorted arrays each of n-elements and distinct. How much time it will take to find middle element of union array?(a) O(1)(b) O(log n)(c) O(n)(d) None of these
1 votes
1 votes
1 answer
3
meethunjadhav asked Jul 30, 2018
406 views
suppose merge sort takes 2 sec to sort a set of 64 keys then how much time will take to sort a set of 512 keys?here, ans is 24 sec how it is plz explain me.
2 votes
2 votes
1 answer
4