Question

(a) Implement a sublinear running time complexity recursive function in Java public static long long x, int n) to calculate X 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 x63.

Please code this in Java, thank you!

Answer 1

Answer (a)

PROGRAM :

import java.io.*;

public class ExponentialPower
{
  
public static void main(String args[]) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

ExponentialPower func = new ExponentialPower();

System.out.println("Enter the value of x (Number) :"); // Taking Input
long x = Integer.parseInt(br.readLine());

System.out.println("Enter the value of n (Power :"); // Taking Input
int n = Integer.parseInt(br.readLine());

System.out.println("\n" +x +"^" +n +" = "+func.exponentiation(x,n)); // Method Called
}


public static long exponentiation(long x, int n)
{
if(n==0)
return 1;

else if(n==1)
return x;

else
return x*exponentiation(x,n-1);
}

}

Answer (b)

TIME COMPLEXITY :

Let's now assume n is of the form n-2k where k E N Λ k > 0 (e.g. n is a power of 2). We then get a recurrence relation like so: log2 n - c(n -1) e(n)

Answer (c)

/*

Let us take x = 2 and n = 63.
Then, multiplication used by the functions :
2*exp(2,62)
2*2*exp(2,61)
2*2*2*exp(2,60)
2*2*2*2*exp(2,59)
.
.
.
.
. and so on upto
2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*exp(2,1)

2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2 = 2^63 = 9.223372e+18

*/

OUTPUTS :

Output - JavaApplication1 (run) X Enter the value of x (Number) Enter the value of n (Power ЕЗ 2 63 BUILD SUCCESSFUL (total time: 5 seconds) 32:3 INS

Output JavaApplication1 (run) X Enter the value of x (Number) Enter the value of n (Power: 5^3 = 125 BUILD SUCCESSFUL (total time: 5 seconds) 6:23 INS