$30.00
Description

Order the following functions by order of growth starting with the slowest. n^{0:1}, 2^{2}^{n} , 5n, (log n)^{5}, n^{5}, 5, 5^{n}, n!, 4^{log} ^{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) = n^{2} for all n 1:
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 pseudocode 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.