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

Question

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);
}
}

Explanation / Answer

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);
}

Time Complexity:

    T(n) = 2T(n/2) + Constant

        = O(n)
    Number of multiplications: n

----------------------------------------------------------------------------------------------------
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);
}

Time Complexity, T(n) = T(n-1) + Constant
                    = O(n)

            Number of multiplications = n
-----------------------------------------------------------------------------------------------------
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);
}
}

TIme Complexity = T(n/2) + Contant
                   = O(logn)
Number of multiplications = O(logn)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.