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.
Consider the following sum: S(n) = sum S(n) is (f(n)). Explain why.
P
n
i=1 log i. Give a simple function f(n) so that the
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.
Prove by induction:
n
X(2i 1) = n2 for all n 1:
1=1
5. 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.
1
