[SOLVED] Java algorithm Imperial College London Department of Computing

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(N1)/2 x(N1)/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