Problem #3

(a) Implement a sublinear running time complexity recursive function in Java

public static long exponentiation(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 x⁶³.