Discrete Mathematics for Computer Science - Spring 2005
Homework 4

Hint for Pr.2, above: try defining a = log n, and express the functions in terms of a.

Page 130
10. Try to find the algorithm with the best asymptotic running time you can, prove that it is correct, and give an asymptotic upper bound on the running time. A correct analysis of an O(n) algorithm is fine for this problem, but extra credit for correct solutions with running time better than O(n)!

Pages 151-152

Pages 142-144
6, 22a, 22f, 24e. Explictily find an appropriate pair of constants C,k in each case.