Question

Problem 3:

(a) 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 /).

(b) What is the running time complexity of your function? Justify.

(c) Give a number of multiplications used by your function to calculate x^63.

Important Notes:

• For the item (a):

o You must add the main method in your program in order to test your implementation.

o You can assume that there are no data errors that need to be checked as all the data will be assumed correct.

o Your function you can use only the basic arithmetic operators (+, -, *, %, and /).

o Your program MUST be submitted only in source code form (.java file).

o Remember that a program that does not compile or does not run loses all correctness points.

Answer 1

SOURCE CODE:

*Please follow the comments to better understand the code.

**Please look at the Screenshot below and use this code to copy-paste.

***The code in the below screenshot is neatly indented for better understanding.



public class Exponentiation
{
    public static long exponentiation(long x, int n)
    {
        // Base cases here
            if (n == 0)
                return 1;

            if (n == 1)
                return x ;

            // recursive function
            long temp = exponentiation(x, n / 2);
            temp = (temp* temp);

            // if exponent is even value
            if (n % 2 == 0)
                return temp;
            else // if exponent is odd value
                return x*temp;
    }

    // test the method
    public static void main(String[] args)
    {
        System.out.println("3^4 is :"+exponentiation(3,4));
        System.out.println("2^10 is :"+exponentiation(2,10));
        System.out.println("10^3 is :"+exponentiation(10,3));
        System.out.println("123^3 is :"+exponentiation(123,3));
    }
}

======================

OUTPUT

1. The time complexity is: O(Log₂ N) N is the exponent
2. To calculate x⁶³, we will perform like this:
   • x⁶³ = x³¹ * x³¹ * x