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.
Answer:
(a)
1: procedure Pow(x, n)
2: if n == 1 then
3: return x
4: end if
5: tmp = Pow(x, n/2) . integer division
6: if n mod 2 == 0 then
7: return tmp× tmp
8: end if
9: return tmp× tmp× x
10: end procedure
Key feature: Pow should be called recursively ONCE, in line 5. If it is called
more than once then the complexity will be Θ(N).
(b)
T (N) =
{
Θ(1) , if N = 1
T (bN/2c) + Θ(1) , if N > 1
1
So, c = 1. Symbols representing constants would be acceptable in place of the
Θ(1) terms. The second formula must include bN/2c, not N/2. The expression
is not correct for all N if it uses T (N/2).
(c) To apply the master method you need to first substitute the recurrence into the
expression T (N) = aT (N/b) + f(N), while ignoring any floors or ceilings. This
gives us a = 1, b = 2 and f(N) = Θ(1). Then compute N logb a, which in this case
is N0 = 1. So, N logb a = Θ(1) and f(N) = Θ(1) = Θ(N logb a log02N). Therefore,
Case 2 of the master method applies and T (N) = Θ(N logb a log2N) = Θ(log2N).
2