Homework Sourse4 Consider the following two different algorithms to raise a
4. Consider the following two different algorithms to raise an integer x to a power of n:
1)
long pow2(long x, int n)
{
if( n == 0 )
return 1;
if( n == 1 )
return x;
if( isEven( n ) )
return pow2( x * x, n / 2 );
else
return pow2( x * x, n / 2 ) * x;
}
bool isEven(int n)
{
return n % 2 == 0;
}
2)
long pow1(long x, int n)
{
if( n == 0 )
return 1;
result= 1;
for(i=0; i< n; i++)
result=result*x
return x; }
1/2
Questions:
(a) Analyze the computational complexity of both algorithms in terms of Big-O notation.
(b) Which algorithm is more efficient?
4. Consider the following two different algorithms to raise an integer x to a power of n:
1)
long pow2(long x, int n)
{
if( n == 0 )
return 1;
if( n == 1 )
return x;
if( isEven( n ) )
return pow2( x * x, n / 2 );
else
return pow2( x * x, n / 2 ) * x;
}
bool isEven(int n)
{
return n % 2 == 0;
}
2)
long pow1(long x, int n)
{
if( n == 0 )
return 1;
result= 1;
for(i=0; i< n; i++)
result=result*x
return x; }
1/2
Questions:
(a) Analyze the computational complexity of both algorithms in terms of Big-O notation.
(b) Which algorithm is more efficient?
4. Consider the following two different algorithms to raise an integer x to a power of n:
1)
long pow2(long x, int n)
{
if( n == 0 )
return 1;
if( n == 1 )
return x;
if( isEven( n ) )
return pow2( x * x, n / 2 );
else
return pow2( x * x, n / 2 ) * x;
}
bool isEven(int n)
{
return n % 2 == 0;
}
2)
long pow1(long x, int n)
{
if( n == 0 )
return 1;
result= 1;
for(i=0; i< n; i++)
result=result*x
return x; }
1/2
Questions:
(a) Analyze the computational complexity of both algorithms in terms of Big-O notation.
(b) Which algorithm is more efficient?
(a) Analyze the computational complexity of both algorithms in terms of Big-O notation.
(b) Which algorithm is more efficient?
Solution
(a) For the first algorithm time complexity is O(logn). Because, It uses divide and conquer. It divides given problem of size n into two subproblems of size n/2 and solve only one subproblem using the decision of whether the given number is even or not.
For the second algorithm time complexity is O(n). Because we are using one for loop and iterating it over n times.
(b) First algorithm is more efficient because it\'s time complexity is less.
