saygapro
asked on
Help with divide and conquer recursion
Hello, I am looking for sample recursion questions and there is one that involves writing a recursive exponent program in java. The method takes in two integers. 1 being the base number and the other being the exponent. The method returns an integer.
int exponent(int x, int n) so x = 2 and n = 4 would return 16.
The catch is that the recursive method has to be done using divide and conquer. I have attempted the problem below but I am wondering if my code has the complexity of O(log n)?. My thinking for divide and conquer is this:
pow(2, 4)
/ \
/ \
pow(2, 2) pow(2,2)
/ \ / \
pow(2,1) pow(2,1) pow(2,1) pow(2,1)
/ \ / \
return n * return n * return n * return n
Here is my code:
public static int dcpow(int x, int y)
{
if ( y == 1)
return x;
else
return dcpow(x,y/2) * dcpow(x,y/2);
}
Is this how you would use divide and conquer on this problem?
Is my code O(log n) and could someone throughly help me understand why it is?
Also, I have been trying to do Fibonacci recursively using divide and conquer. Can someone help me code this problem?
Thank you.
int exponent(int x, int n) so x = 2 and n = 4 would return 16.
The catch is that the recursive method has to be done using divide and conquer. I have attempted the problem below but I am wondering if my code has the complexity of O(log n)?. My thinking for divide and conquer is this:
pow(2, 4)
/ \
/ \
pow(2, 2) pow(2,2)
/ \ / \
pow(2,1) pow(2,1) pow(2,1) pow(2,1)
/ \ / \
return n * return n * return n * return n
Here is my code:
public static int dcpow(int x, int y)
{
if ( y == 1)
return x;
else
return dcpow(x,y/2) * dcpow(x,y/2);
}
Is this how you would use divide and conquer on this problem?
Is my code O(log n) and could someone throughly help me understand why it is?
Also, I have been trying to do Fibonacci recursively using divide and conquer. Can someone help me code this problem?
Thank you.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
if( y==0 ) return 1;
p = dcpow(x,y/2);
p = p*p;
if( y/2 + y/2 < y ) p=p*x;
return p;
which is O(log n) instead of O(n)