For this problem consider raising an integer a to the power n (another non-negative integer). Mathematically we use an e

[answerhappygod]

For This Problem Consider Raising An Integer A To The Power N Another Non Negative Integer Mathematically We Use An E 1 (57.89 KiB) Viewed 39 times

For this problem consider raising an integer a to the power n (another non-negative integer). Mathematically we use an express the output to this problem. Sometimes in a computer science context we might use EXP(a,n) to express the same output. You can use whichever notation you find most comfortable for your solution. a) Express this problem formally with an input and output. b) Write a simple algorithm using pseudocode and a loop to solve this problem. How many integer multiplications does your algorithm make in the worst case? c) Now use the divide and conquer design strategy to design a self-reduction for this problem. (Hint: It might help to consider the cases when n is even and odd separately.) d) State a recursive algorithm using pseudocode based off of your self-reduction that solves the problem. e) Use big-Theta notation to state a tight bound on the number of multiplications used by your algorithm in the worst case.