How to find the number of multiplications for x^63 using the exponent recursive function and how to justify it?

Question

How would I go about justifying this algorithm is O(log n)?

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

    if(n == 0){
        return 1;
    }
    else if (n % 2 == 0){
        x = exponentiation(x, n / 2);
        return x * x; 
    }
    else{
        return x * exponentiation(x, n-1);
    }
}

Answer 1

Each recursive call to method exponentiation is a multiplication step. Hence you need to count the number of recursive calls. There are several ways to achieve this. I chose to add another parameter to the method.

public static long exponentiation(long x, int n, int count) {
    if (n == 0) {
        System.out.println("steps = " + count);
        return 1;
    }
    else if (n % 2 == 0) {
        x = exponentiation(x, n / 2, count + 1);
        return x * x; 
    }
    else {
        return x * exponentiation(x, n - 1, count + 1);
    }
}

Here is the initial call to method exponentiation

exponentiation(2, 63, 0);

When I run the above code, the following is printed

steps = 11