algorithm runtime divide-and-conquer master-theorem

Divide and Conquer to solve the power of a number, runtime analysis with master theorem

I implemented a divide and conquer algorithm to calculate the power of a number:

public static void main(String[] args) {
    System.out.println("Result: " + pow(2, 1));
    System.out.println("Result: " + pow(2, 9));
    System.out.println("Result: " + pow(2, 8));
    System.out.println("Result: " + pow(2, 0));
}

private static int pow(int n, int pow) {
    if(pow == 0) {
        return 1;
    }

    if(pow > 2) {
        int leftPow;
        int rightPow;

        if(pow % 2 != 0) {
            leftPow = pow/2;
            rightPow = pow/2+1;
        } else {
            leftPow = pow/2;
            rightPow = leftPow;
        }

        return pow(n, leftPow) * pow(n, rightPow);
    } else {
        if(pow == 1) {
            return n;
        } else {
            return n * n;
        }
    }
}

My method seems to work, since the output is:

Result: 2
Result: 512
Result: 256
Result: 1

Now Iam trying to determine the runtime of my algorithm using the Master-Theorem:

$T(n) = a*T(n/b)+f(n)$

I assume, that

$a=2$ , since the recursive call appears two times,

$b=2$ , since Iam creating two subproblems out of one problem

and $f(n) = 1$ , since combining the results takes constant time.

The watershed constant ( $log_{b}a$ ) should be $\alpha = 1$ .

With these values, I assume that the first rule of the Theorem holds: $f(n) = O(n^{\alpha-\varepsilon })$ , with $\varepsilon = 1$ , since $f(n) = O(n^{1-1}) = 1$ .

Therefore the runtime should be: $T(n)=\Theta (n^{\alpha}) = \Theta (n)$ .

Iam quite unsure about this result, since I never had the case $f(n) = 1$ .

Is my analysis correct?

Solution

First, you should notice that the complexity will be explained based on the pow. So, n in your analysis means pow not n variable in your program.

Second, as the number of computations such as comparison and multiplying is constant (less than 10 for your program), so f(n) = \Theta(1) and you can write it f(n) = 1 here.

Therefore, the complexity is T(n) = 2T(n/2) + 1 (you can see Akra-Bazzi method too), and T(n) = \Theta(n).