Question

Implement a sublinear running time complexity recursive function in Java public static long exponentiation (long x, int n) to calculate x^n. Note: In your function you can use only the basic arithmetic operators (+, -, *, and /).

Answer 1

Answer:

Following are the code block in the Java Programming Language.

//define recursive function

public static long exponentiation(long x, int n) {

//check the integer variable is equal to the 0.

if (x == 0) {

//then, return 1

return 1;

}

//Otherwise, set else

else {

//set long data type variable

long q = exponentiation(x, n/2);

q *= q;

//check if the remainder is 1

if (n % 2 == 1) {

q *= x;

}

//return the variable

return q;

}

}

Explanation:

Following are the description of the code block.

• Firstly, we define the long data type recursive function.
• Then, set the if conditional statement and return the value 1.
• Otherwise, set the long data type variable 'q' that sore the output of the recursive function.
• Set the if conditional statement and check that the remainder is 1 and return the variable 'q'.