(1a) Order the following functions by the big-O notation. Group together in parenthesis those functions which are of each other (short answer: no proofs are needed): 6n log2 n, 2100, log log n, log2 n, 2log n , 22 n , d ne, n 1/2 , n .01, 1/n, 2n , n log4 n, 4 log2 n , 4log3 n , log n, 4n , 2n , 4n 3/2 .

(1b) What is the asymptotic running time of the following loops? (Recall that you are in the RAM model where words have size O(log n)). Prove that your anwer is correct by giving a recurrence and a proof using induction: a) Loop1(n): x 2; for i 1 to 2n do x x i b) Loop2 (n): x 2; for i 1 to 2n do x x x

(1c) Modify the 2 Wand problem from Lecture 1 so that there are k, for k = 1, ..., n wands. Give the pseudocode for the efficient algorithm you can find. Analyze its asymptotic cost.