Help with divide and conquer recursion

Posted on 2008-02-11
Medium Priority
Last Modified: 2012-06-21
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;
          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.
Question by:saygapro
  • 2
LVL 53

Accepted Solution

Infinity08 earned 210 total points
ID: 20864809
>>           return dcpow(x,y/2) * dcpow(x,y/2);

Be careful. This will only work if y is a multiple of 2 (even). If y is odd, then you have to split it up in two unequal parts. Something like :

        int split = y / 2;
        return dcpow(x, split) * dcpow(x, y - split);

>> Is this how you would use divide and conquer on this problem?

You could indeed do it that way, yes.
LVL 85

Assisted Solution

ozo earned 165 total points
ID: 20864852
if( y==0 ) return 1;
if ( y == 1)
             return x;
          return dcpow(x,y/2) * dcpow(x,(y+1)/2);
LVL 85

Expert Comment

ID: 20865135
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)

Featured Post

Take Control of Web Hosting For Your Clients

As a web developer or IT admin, successfully managing multiple client accounts can be challenging. In this webinar we will look at the tools provided by Media Temple and Plesk to make managing your clients’ hosting easier.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses
Course of the Month3 days, 4 hours left to enroll

600 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question