Computers and Technology
Exercise 1. (efficient power) Last assignment, we had a function able to calculate the power by multiplying every time the base, which leads to the following Oz function: declare fun Power N M) if M-= 0 then 1 else N Power N M-1) end end For example, (Power 2 8) returns 256 after 8 recursive calls. The complexity of this function is O(M), since there are M recursive calls, each responsible for one multiplication operation. Write a more efficient version of Power, by reusing the intermediate results. For example, the previous computation may be done using only 3 multiplications, namely 2-22, 2-(2) (2), 2(2 (2) What will be the complexity of this efficient algorithm?