Problem Set 3-a
Problem 1 Show that if p(n) is a polynomial in n, then log p(n) is O(log n).
Problem 2 Show that ∑ 𝑖2𝑛𝑖=1 is O(n
3).
Problem 3 Show that ∑
𝑖
2𝑖
𝑛
𝑖=1 is O(1).
Problem 4 Show that ∑ log 𝑖𝑛𝑖=1 is O(n log n).
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?
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?
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).
Problem 8 The Tower of Hanoi is a classical problem which can be solved by recurrence. There are
three pegs and N disks of different sizes. Originally, all the disks are on the left peg, stacked in
decreasing size from bottom to top. Our goal is to transfer all the disks to the right peg, 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
easily solve this problem with the following recursive algorithm: If N = 1, move this disk directly to the
right peg and we are done. Otherwise (N >1), first transfer the top N-1 disks to the middle peg applying
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?
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?