The goal for this exercise is to review recursion, and to think about how one can apply the “Big Oh” notation to not just time consumed, but also space consumed by an algorithm.
Given the code sample below, first figure out what Pow1 & Pow2 will print (and more importantly, how they will print). Make sure that you find the running time of the two implementations, in O(N) notation, where N is the exponent parameter. Also, see if you can figure out how much space each implementation uses, again using the O(N) notation.
class
Two_Pow_Implementations Console.WriteLine(" ****** Pow1 Tests: ******\n"); Console.WriteLine("3^0: {0}", Two_Pow_Implementations.Pow1(3, 0)); Console.WriteLine("3^1: {0}", Two_Pow_Implementations.Pow1(3, 1)); Console.WriteLine("3^3: {0}", Two_Pow_Implementations.Pow1(3, 3));
Console.WriteLine("2^6: {0}", Two_Pow_Implementations.Pow1(2, 6)); Console.WriteLine("17^2: {0}", Two_Pow_Implementations.Pow1(17, 2)); Console.WriteLine("-2^3: {0}", Two_Pow_Implementations.Pow1(-2, 3));
Console.WriteLine(" ****** Pow2 Tests: ******\n"); Console.WriteLine("3^0: {0}", Two_Pow_Implementations.Pow2(3, 0)); Console.WriteLine("3^1: {0}", Two_Pow_Implementations.Pow2(3, 1)); Console.WriteLine("3^3: {0}", Two_Pow_Implementations.Pow2(3, 3));
Console.WriteLine("2^6: {0}", Two_Pow_Implementations.Pow2(2, 6)); Console.WriteLine("17^2: {0}", Two_Pow_Implementations.Pow2(17, 2)); Console.WriteLine("-2^3: {0}", Two_Pow_Implementations.Pow2(-2, 3));
Console.WriteLine(); }
// This method calculates bas raised to the power of exponent // (aka bas ^ exponent) // It does this iteratively public static double Pow1(double bas, uint exponent) { double retVal = 1; for (int i = 0; i < exponent; i++) { retVal *= bas; } return retVal; }
// This method also calculates bas raised to the power of exponent // (aka bas ^ exponent) // It does this recursively public static double Pow2(double bas, uint exponent) { if (exponent == 0) return 1; if (exponent == 1) return bas;
// Assume that IsPowerOfTwo returns true when // exponent is an even power of 2 – 2, 4, 8, 16, 32, 64, etc // and false when exponent is anything else // Assume that it will run in constant time (if you’ve seen // Big Oh notation – if not, ignore this last line ? ) if ( IsPowerOfTwo(exponent) != true) return bas * Pow2(bas, exponent - 1); else return Pow2(bas * bas, exponent / 2); } } |
What you need to do for this exercise:
Student_Answers.cs
, there is a
class named Two_Pow_Implementations.