Link to home
Start Free TrialLog in
Avatar of saygapro
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.
ASKER CERTIFIED SOLUTION
Avatar of Infinity08
Infinity08
Flag of Belgium image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
It would be more efficient to do something like
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)