Test your algorithms solutions in Java at http://codingbat.com/prob/p158888

Compare the results of your three solutions down below and assess which does more or less work.

1.Develop a transform-and-conquer algorithm for the calculation. Describe your idea used in the transformation. Evaluate your algorithm to determine the number of multiplications performed overall.

Solution# 1

public int powerN(int base, int n) {

if (n == 0) return 1;

if (n % 2 == 0) return powerN(base,n/2)*powerN(base,n/2);

else return base*powerN(base,n/2)*powerN(base,n/2);

}

----------------------------------------------------------------------------------------------------

2.Present a brute-force algorithm for the calculation and show the number of multiplications performed overall.

Solution# 2

public int powerN(int base, int n) {

if (n == 0) return 1;

return base*powerN(base,n-1);

}

-----------------------------------------------------------------------------------------------------

3.Develop a recursive reduce-by-one algorithm for the calculation, establish and solve the recurrence relation for the number of multiplications performed overall.

Solution# 3

public int powerN(int base, int n) { // at the end return n == 0 return 1 if (n == 0) { return 1; } else { return base * powerN(base, n - 1); } }