Question 2.
13 PN
How much time is used to compute f (x) = i=0 ai xi :
a) using the “dumb” exponentiation algorithm?
b) using the “fast” exponentiation algorithm?
Solution
Let c be any integer between 1 and N .
a) Using “dumb” exponentiation
PN
c multiplications are used to compute ac xc . Therefore i=0 i multiplications
PN
are used to compute i=0 ai xi (as well as N additions). Therefore the number
of operations used to compute f (x) is:
N
X
= (i) + N
i=0
N (N + 1)
= +N
2
2
= O(N )
b) Using “fast” exponentiation
PNApproximately log2 c multipications are used P to compute ac xc . Therefore
N i
i=1 log2 i multiplications are used to compute i=1 ai x (as well as N ad-
ditions). Therefore the number of operations used to compute f (x) equals:
N
X
= log2 i + N
i=1
= log2 1 + log2 2 + log2 3 + ... + log2 N + N
= log2 1 × 2 × 3 × ... × N + N
= log2 N ! + N
= O(logN !)
Question 2.14 Consider the following algorithm(known as Horner’s rule)
PN
to evaluate f (x) = i=0 ai xi :
poly = 0;
for( i = n; i >= 0; i − − )
poly = x × poly + a[i];
a) Show how the steps are performed by this algorithm for x = 3, f (x) =
4x4 + 8x3 + x + 2.
b) Explain why this algorithm works
c) What is the running time of this algorithm?
Solution
a) The values of the multiplicative constants are, a0 = 2, a1 = 1, a2 = 0, a3 =
8, a4 = 4 and x = 3. Now using these just step through the loop one iteration at
a time.
b)
f (x) can be rewritten as follows:
f (x) = (an xn + an−1 xn−1 + an−2 X n−2 + ... + a2 x2 + a1 x + a0 )
= (x(an xn−1 + an−1 xn−2 + an−2 xn−3 + ...a2 x + a1 ) + a0 )
= (x(x(an xn−2 + an−1 xn−3 + an−2 xn−4 + ...a2 ) + a1 ) + a0 )
=.
=.
=.
= (x(x(x(...x(x(x(an ) + an−1 ) + an−2 )...) + a2 ) + a1 ) + a0 )
Observe that the sum of the value of the expression inside the ith innermost
brackets, equals the value of poly after i iterations. Therefore the value of the
expression inside the (n+1)th inner most brackets( i.e. the outer brackets) equals
the value of poly after n + 1 steps. But this also equals the value of f (x).
c) O(N ) - because the for loop iterates N + 1 times, with a constant amount
of work at each iteration.
Question 2.15
Give an efficient algorithm to determine if their exists an integer i such that
Ai = i in an array of integers A1 < A2 < A3 < ... < AN . What is the running
time of your algorithm?
Solution
Let c be an integer between 1 and N . Observe that,
– if Ac < c, then Ai < i, for i = 1 to (c − 1).
– if Ac > c, then Ai > i, for i = (c + 1) to N
Algorithm:
Check if the middle element satisfies Ai = i, and if it does the answer is yes.
If Ai < i we can apply the same strategy to the subarray to the right of the
middle element.
If Ai > i we can apply the same strategy to the subarray to the left of the middle
element.
Runtime Analysis:
The problem is halved in size at each step, for a constant amount of work.
Therefore O(logN ).
Question 2.20
a) Write a program to determine if a positive integer, N , is prime.
b) In terms of N , what is the worst case running time of your program?
c) Let B equal the number of bits in the binary representation of N . What is
the value of B?
d) In terms of B, what is the worst-case running time of your program?
e) Compare the running times to determine if a 20-bit and a 40-bit number are
prime
Solution √
a) Test to see if N is 1, 2 or odd and not divisible by 3, 5, 7, ... N .
bool prime test(int N)
{
if (N == 1 || N == 2)
return true;
if ( N%2 == 0 )
return false; √
for(int i = 3; i < N ; i = i + 2)
if ( N%i == 0)
return false;
return true;
}
√
b) One for loop, which iterates√at most N times, with a constant amount
of work each time. Therefore O( N ).
c) With x bits one can represent any number from 0 up to 2x − 1. Therefore N
can be represented with O(log2 N ) bits. √ B
d) B ≈ log2 N . Therefore N ≈ 2B . So the running time is O( 2B ) = O(2 2 ).
20
e) A 20-bit number can be tested in time approximately 2 2 = 210 . A 40-bit num-
40
ber can be tested in time approximately 2 2 = 220 . Observe that 220 = (210 )2 .
f) B is better because it more accurately measures the size of the input.
Question 2.21
The Sieve of Eratosthenes is a method used to compute all primes less than N .
We begin by making a table of integers 2 to N . We find the smallest√integer,
i, that is not crossed out, print i, and cross out i, 2i, 3i, .... When i > N , the
algorithm terminates. What is the running time of this algorithm?
Here are two nice graphical explanations of the sieve method
– MathWorld’s page
– scroll down to table on this page
Solution
// Sieve of Eratosthenes: at end of function the bool array ’prime’
// contains all of the prime numbers marked true; that is
// prime[i] = true if and only if i is prime
void sieve(int n)
{
bool prime[n+1]; // indices 0..n
prime[0] = prime[1] = false; // set these initially
for (int i = 2; i <= n; i++)
prime[i] = true; // initialise remainder to true
for (int p = 2; p <= sqrt(n); p++)
{
if (prime[p] == false) continue; // ignore non-primes
for (int k = 2; k*p <= n; k++) // loop iterates n/p times
{
int c = k*p; // c is composite, non-prime
prime[c] = false;
}
}
}
The number of steps taken to work out all the primes from 1 to n is equal
to the number of times you cross out an integer (note some integers get crossed
out more than crossed out more than once e.g. 21 = 3 ∗ 7, gets crossed out for
i = 3 and√i = 7). The inner loop gets triggered once for√every prime less than
or equal n. You√didn’t know this but there are ≈ log n prime numbers less
than or equal to n.
The work done by the inner loop (number of iterations) when working with
p is N/p. Over the entire lifetime of the algorithm this will amount to N/2 √ +
N/3 + N/5 + · ·√· + N/q , where q is the last prime no. less than or equal to N .
(There are log N terms.) This is √ equal to N times the sum of the reciprocals
of the primes
√ less than or equal to N and is less than N times the sum of the
first log N reciprocals, which is the harmonic number Hlog √N whose size we
√
√ is ≈ log log N . Therefore the running time of this algorithm is
said in Lect01
O(N log log N ).
Question 2.22
Show that X 62 can be computed with only eight multiplications.
Solution
X 62 = X 40 × X 20 × X 2
X 40 = X 20 × X 20
X 20 = X 10 × X 10
X 10 = X 8 × X 2
X8 = X4 × X4
X4 = X2 × X2
X2 = X × X
Note that this is better than even the exponentiation by binary decomposi-
tion method. It doesn’t work in general though.
Question 2.24
Give a precise count on the number of multiplications used during the fast ex-
ponentiation routine. (Hint: consider the binary representation of N .)
Solution
For N = 0 or N = 1 the number of multiplications is zero.
For N > 1. Let b(N ) = the number of ones in the binary representaion of N.
It is possible to convert a number in base 10 to a number in base by succes-
sive division by 2.
E.g. Converting 13510 to base 2.
135/2 = 67remainder1
67/2 = 33remainder1
33/2 = 16remainder1
16/2 = 8remainder0
8/2 = 4remainder0
4/2 = 2remainder0
2/2 = 1remainder0
1/2 = 0remainder1
Thus the number 13510 in binary is 10000111.
To work out X 135 using the fast exponientation algorithm the following steps
are taken:
X 135 = X 67 × X 67 × X
X 67 = X 33 × X 33 × X
X 33 = X 16 × X 16 × X
X 16 = X 8 × X 8
X8 = X4 × X4
X4 = X2 × X2
X2 = X × X
Notice that the number of times two multiplications are needed at a step,
rather than 1, is equal to b(N ) − 1. Thus the number of multiplications used to
evaluate X N equals the number of steps, blogN c, plus the number of ones in the
binary representation, b(N ), minus 1.
So the answer is:
blogN c + b(N ) − 1
Question 2.25
Programs A and B are analyzed and found to have worst-case running times
no greater 150N log2 N and N 2 , respectively. Answer the following questions, if
possible:
a) Which program has the better guarantee on running time, large values of
N (N > 10, 000)?
b) Which program has the better guarantee on running time, small values of
N (N < 100)?
c) Which program will run faster on average for N = 1000?
d) Is it possible that program B will run faster than program A on all possible
inputs?
Solution
a) A
b) B
c) Not enough information given to answer this question.
d) Yes.
