###
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

8

Pages 142-144

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