[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(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