Homework 4

Details

Homework 4

Due January 31, 2006

Your work should be clear, concise, and in the order given.No scratched-out work, etc. should be present on your assignment.Illegible or messy work may result in a reduction in points. It is recommended that you learn and use some computer typesetting software (e.g. Word or LaTeX).

Section	Page	Problem	Points
2.2	60	61	8
2.3	68	6	5
2.3	69	10	3
Ranking2			9
Total			25

Notes:

1. For part a, prove upper and lower bounds. For part b, you want to prove that for anypositive constants a and b with a< b, that aⁿ is O(bⁿ), but that bⁿ is not O(aⁿ).
2. Ranking Rank the following functions in increasing order of growth, clearlyindicating ties:
   • n
   • (n-2)!
   • n²
   • log n
   • n - n³ + 7n⁵
   • n² + n log n
   • eⁿ .5
   • 2^n-1
   • log log n
   • n³
   • ln n
   • 2ⁿ
   • (log n)³
   • n!
   • n^1+e (0 < e < 1)
   • n log n
   • 5 log ((n+5)²⁰)
   • .00001n⁴ + 20000n³
   • n^1/3
   • 5ⁿ