Problem Set3-a Solutions
Problem 1 Show that if p(n) is a polynomial in n, then log p(n) is O(log n).
Solution: Let p(n) = amnm + am-1nm-1 + … + a1n + a0
p(n) < max{|am|, |am-1|, …, |a0|} (m+1) n
m
log p(n) < log(max{|am|, |am-1|, …, |a0|} (m+1) + m log n
Since m and ai (i=0, 1, …, m) are constants, we have O( log p(n)) = O(log(max{|am|, |am-1|, …,
|a0|}) (m+1)+ O(m log n) = O(log n).
Problem 2 Show that 12+ 22+ ... + n2
is O(n3) .
Solution 1: The area of the shape enclosed by the x-axis, the vertical line x=0, the vertical line
x=n+1, and the curve y=x2, is given by ∫ 𝑥2
𝑛+1
0
𝑑𝑥. This shape contains every rectangle formed by the
four lines x=i, x=i+1, y=0 and y=i2 (i=1, 2, …, n). Therefore, we have the following inequality:
∑ 𝑖2 < ∫ 𝑥2𝑑𝑥
𝑛+1
0
𝑛
𝑖=1
∫ 𝑥2𝑑𝑥 =
(𝑛+1)3
3
𝑛+1
0
= 𝑂(𝑛3)
Solution 2: 12+ 22+ ... + n2 = n(n+1)(2n+1)/6=n3/3+n2/2+n/6=O(n3).
Problem 3 Show that ∑
𝑖
2𝑖
𝑛
𝑖=1 is O(1).
Solution: Let 𝑆 = ∑
𝑖
2𝑖
𝑛
𝑖=1 . 𝑠 = ∑
𝑖
2𝑖
𝑛
𝑖=1 = ∑
1
2𝑖
𝑛
𝑖=1 + ∑
𝑖−1
2𝑖
𝑛
𝑖=2 = ∑
1
2𝑖
𝑛
𝑖=1 + ∑
𝑖
2𝑖+1
𝑛−1
𝑖=1 < 1 + 𝑠/2 .
Therefore, S<2. As a result, ∑
𝑖
2𝑖
𝑛
𝑖=1 is O(1).
Comments: It is easy to prove ∑
1
2𝑖
𝑛
𝑖=1 <1. Let A = ∑
1
2𝑖
𝑛
𝑖=1 . 2A = ∑
2
2𝑖
𝑛
𝑖=1 = ∑
1
2𝑖−1
𝑛
𝑖=1 = 1 + ∑
1
2𝑖
𝑛−1
𝑖=1
<1+A. Threfore, A<1.
Problem 4 Show that ∑ log 𝑖𝑛𝑖=1 is O(n log n).
Solution: ∑ log 𝑖 < 𝑛𝑙𝑜𝑔𝑛𝑛𝑖=1 = 𝑂(𝑛𝑙𝑜𝑔𝑛)
Problem 5 Consider the following algorithm:
Algorithm Unknown(A, B)
Input: Arrays A and B each storing n>0 integers.
Output: The number of elements in B equal to the sum of prefix sums in A.
c=0;
for i=0 to n-1 do
{ s=0;
for j=0 to n-1 do
{ s=s+A[0];
for k=0 to n-1 do
s=s+A[k];
}
if ( B[i]=s )
c=c+1;
}
return c;
What is the time complexity of this algorithm in big-Oh notation?
Solution: The number of primitives of each statement is shown as follows.
Statements Number of primitive operations of each statement
c=0; 1
for i=0 to n-1 do n
{ s=0; n
for j=0 to n-1 do n2
{ s=s+A[0]; n2
for k=0 to n-1 do n3
s=s+A[k]; n3
}
if ( B[i]=s ) n
c=c+1; n
}
return c; 1
The total number of primitives is 2n3+2n2+4n+2=O(n3).
Problem 6 Consider the following algorithm:
Algorithm MatrixMultiplication(A, B)
Input: Matrices A[m,k] and B[k,n].
Output: A matrix C= A*B.
for i=0 to m-1 do
{
for j=0 to n-1 do
{ c[i,j]=0;
for p=0 to k-1 do
c[i,j]+=A[i,p]*B[p,j];
}
}
return C;
What is the time complexity of this algorithm in big-Oh notation?
Solution: The number of primitives of each statement is shown as follows.
Statements Number of primitive operations of each statement
for i=0 to m-1 do m
{
for j=0 to n-1 do m*n
{ s=0; m*n
for p=0 to k-1 do m*n*k
c[i,j]+=A[i,p]*B[p,j]; m*n*k
c[i,j]=s; m*n
}
}
return C; 1
The total number of primitives is m + m*n + m*n + m*n*k + m*n*k + m*n=O(m*n*k).
Problem 7 Let p(x) be a polynomial of degree n, where p(x)= anx
n + an-1x
n-1 + … + a1x + a0. Design an
O(n)-time algorithm for computing p(x).
Solution: Rewrite p(x) as p(x) = (…((anx
+ an-1)x + an-2)x
+ … + a1)x + a0, which can be recursively
computed as follows: p0=an, pi+1=pi x+ ai (i=0, 1, …, n-1). The algorithm is as follows:
Algorithm computingPloynomial(x, n, A[])
Input: A polynomial where all the coefficients are stored in a one-dimensional array A of size n+1 and
x stores the value of the variable.
Output: The result of the polynomial for x.
p= A[n];
for (i=1; i
the algorithm recursively, then move the largest disk to the right peg, and finally transfer the N-1 disks
on the middle peg to the right peg applying the algorithm recursively. Let T(N) be the total number of
moves needed to transfer N disks. We have that T(1) = 1, and T(N) = 2T(N-1)+ 1. What is the time
complexity of this algorithm in big-Oh notation?
Solution: T(N) = 2(2T(N − 2) + 1) + 1
= 4T(N − 2) + 2 + 1
= 4(2T(N − 3) + 1) + 2 + 1
= 8T(N − 3) + 4 + 2 + 1
= …
= 2(N−1)T(1) + 2N−2 + …+ 2+1
= 2(N−1)T(1) + 2N−1 −1
= 2N − 1
Therefore, the time complexity of this algorithm is O(2N).
Problem 9 The Towers of Providence is a variation of the classical Towers of Hanoi problem. There
are four pegs, denoted A, B, C, and D, and N disks of different sizes. Originally, all the disks are on
peg A, stacked in decreasing size from bottom to top. Our goal is to transfer all the disks to peg D, and
the rules are that we can only move one disk at a time, and no disk can be moved onto a smaller one.
We can solve this problem with a recursive algorithm: If N = 1,move this disk directly to peg D,
and we are done. Otherwise (N > 1), perform the following steps:
1. transfer the top N-2 disks on peg A to peg B applying the algorithm recursively;
2. move the second largest disk from peg A to peg C;
3. move the largest disk from peg A to peg D;
4. move the second largest disk from peg C to peg D;
5. transfer the N-2 disks on peg B to peg D applying the algorithm recursively.
Let T(N) be the total number of moves needed to transfer N disks. We have:
T(1) = 1; T(N) = 2T(N-2) + 3: What is the time complexity of this algorithm in big-Oh notation?
Solution: T(N) = 2(2T(N − 4) + 3) + 3
= 4T(N − 4) + 3*(2 + 1)
= 4(2T(N − 6) + 3) + 3*(2 + 1)
= 8T(N − 6) + 3*(4 + 2 + 1)
= 2i T(N-2i)+3(2i-1 + …+ 2+1)
Let N-2i =1. We have i=(N-1)/2. Therefore,
T(N) = 2(N−1)/2T(1) + 3*(2(N−1)/2-1 + …+ 2+1)
= 2(N−1)/2T(1) + 3*(2(N−1)/2 − 1)
= 2(N−1)/2 + 3*2(N−1)/2 − 3
= 22*2(N−1)/2 − 3
= 2(N+3)/2 − 3
Therefore, the time complexity of this algorithm is O(2(N+3)/2 − 3) = O(2N).