(a) (10 points) The following pseudocode shows a recursive algorithm for computing 2 for any integer...

Transcribed Image Text:

(a) (10 points) The following pseudocode shows a recursive algorithm for computing 2" for any integer n 20. It is based on the recurrent relationship: 2n = 2n-1+2n-1. Only consider addition as a primitive operation. Use the substitution method to show the running time of this algorithm in big-Oh notation. Algorithm recur Power (n): if (n == 0) then return 1 else // addition as a primitive operation return recurPower (n-1) + recurPower (n-1) (b) (5 points) The following pseudocode shows a non-recursive algorithm for computing 2". Show the running time of this algorithm in big-Oh notation. Here, you can consider multiplication as a primitive operation. Algorithm iter Power (n): if (n == = 0) then return 1 else W return power O power = 1 for (i = 0:n-1) do O // consider multiplication as a primitive operation power = power * 2 2 (a) (10 points) The following pseudocode shows a recursive algorithm for computing 2" for any integer n 20. It is based on the recurrent relationship: 2n = 2n-1+2n-1. Only consider addition as a primitive operation. Use the substitution method to show the running time of this algorithm in big-Oh notation. Algorithm recur Power (n): if (n == 0) then return 1 else // addition as a primitive operation return recurPower (n-1) + recurPower (n-1) (b) (5 points) The following pseudocode shows a non-recursive algorithm for computing 2". Show the running time of this algorithm in big-Oh notation. Here, you can consider multiplication as a primitive operation. Algorithm iter Power (n): if (n == = 0) then return 1 else W return power O power = 1 for (i = 0:n-1) do O // consider multiplication as a primitive operation power = power * 2 2

Answer rating: 100% (QA)

a To analyze the running time of the recurPower algorithm using the substitution method well first d... View the full answer