Explain an algorithm that computes 2^n using Θ(log n) multiplications. Justify why your algorithm uses Θ(log n) multiplications. a. Consider the case where n is a power of 2, i. e., n = 2^k . Use Θ(k) multiplications to obtain 2n . Hint: Note that 2^(2^k) = (2^(2^k−1) )^2 .
b. Consider the case where n = 2^k + 2^(k−1) . Use Θ(k) multiplications to obtain 2^n . Hint: Note that 2^(2^k+2^(k−1)) = 2^(2^k) × 2^(2^(k−1)) .
c. Generalize the ideas in parts (a) and (b) to compute 2n using Θ(log n) multiplications for any positive integer n.