Please code in Java and keep in mind that it is supposed to be running a subline
ID: 3878162 • Letter: P
Question
Please code in Java and keep in mind that it is supposed to be running a sublinear running time complexity! So if the time complexity is O(n) then it is incorrect. It cannot be O(n).
(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.Explanation / Answer
public static long exponentiation(long x,int n)
{
long k;
if(n==0)
return 1;
k = exponentiation(x,n/2);
if(n%2==0)
return k*k;
else
return x*k*k;
}
//complexity will be O(logn)