ASSIGNMENT #1 Solution



  1. Order the following functions by order of growth starting with the slowest. n0:1, 22n , 5n, (log n)5, n5, 5, 5n, n!, 4log n, 2n log log n.

  1. Consider the following sum: S(n) = sum S(n) is (f(n)). Explain why.



i=1 log i. Give a simple function f(n) so that the

  1. Solve Problem 1.4.6 on Page 208 in the textbook. It asks you to give the order of growth (as a function of N) of the running times for three code fragments.

  1. Prove by induction:


X(2i 1) = n2 for all n 1:


  1. An Array A contains n 1 unique integers in the range [0; n 1]. That is, there is one number in this range that is not in A. Describe in pseudo-code an O(n)-time algorithm for nding that number. You are only allowed to use O(log n) bits of additional space besides the array A itself.