Homework 1: Asymptotic notations and proofs of correctness.

Homework 1
The purpose of this homework assignment is to give you additional practice with asymptotic
notations and proofs of correctness. You are asked to solve a few problems that are similar to
the problems discussed in class and tutorials. Please write the solutions to these problems clearly
showing all the work you did to arrive at a solution. For problems that ask you to show or prove
something, please write your proofs succinctly so that your reasoning is easy to follow. Be precise
and do not skip any non-trivial steps. Please also pay attention to punctuation and grammar.
Please submit your solution as a PDF file (scanned or typeset) using the HW1 dropbox on D2L.
1. Asymptotic Notations (10 points):
(a) Prove that if f(n) = O(g(n)) and g(n) = O(f(n)), then f(n) = Θ(g(n)).
(b) Prove that little-o is transitive, i.e. if f(n) = o(g(n)) and g(n) = o(h(n)), then f(n) =
o(h(n)).
(c) Let p(n) = a0 + a1n + a2n
2 + · · · + akn
k where ak 0. Prove that p(n) = Θ(n
k
).
(d) Find two positive valued functions f(n) and g(n) such that neither f(n) = O(g(n)) nor
g(n) = O(f(n)).
2. (5 points)
Weiss (Exercise 2.7 (6)): Using a loop invariant or otherwise, determine the asymptotic complexity
of the following loop. State your answer using an appropriate asymptotic notation.
Please show all the steps that lead you to the asymptotic characterization.
sum = 0;
for ( i = 1; i < n ; i ++ )
for ( j = 1; j < i * i ; j ++ )
if ( j % i == 0 )
for ( k = 0; k < j ; k ++ )
sum ++;
3. (10 points)
Weiss (Exercise 2.14) and CLRS (Problem 2-3): Horner’s rule is an efficient method to evaluate
a univariate polynomial f(x) = Pn
k=0 akx
k
. It is given by the following algorithm:
y ← 0;
for i ← n to 0 do
y ← ai + x · y ;
end
(a) Trace the execution of this algorithm for x = 3 and f(x) = 4x
4 + 8x
3 + x + 2.
1

(b) Consider the following loop invariant:
At the start of each iteration of the for loop:
y =
n−X
(i+1)
k=0
ak+i+1x
k
.
Show that this loop invariant holds by showing the initialization and maintenance steps.
(c) Use the loop invariant above to show the partial correctness of this algorithm.
(d) Analyze the running time of Horner’s rule and state your answer using the most precise
asymptotic notation.
4. (5 points) Identify a suitable loop invariant for the Selection sort algorithm. Use the loop
invariant to prove the partial correctness of Selection sort.