Imperial College London – Department of Computing
MSc in Computing Science
580: Algorithms
Tutorial 2
1. (Part of a 2015 exam question.)
(a) Using either Java or pseudocode, write a recursive procedure Pow(x,N) to compute
xN , where N is a positive integer. Use a divide and conquer strategy. Hint:
xN = xN/2 × xN/2 for even N
xN = x(N−1)/2 × x(N−1)/2 × x for odd N.
(b) Write recurrence expressions for the time complexity T (N) of your Pow procedure
in the following cases:
T (N) =
{
, if 0 < N ≤ c
, if N > c
What is c?
(c) Solve your expressions for T (N) using the master method. Show each step.
1