CS 6363 001 Design and Analysis of Algorithms Spring 2022 Homework 1 Due Feb 3 Professor D T Huynh Problem 1 Do Problem 2 4 Inversions p 41 Text Problem 2 Compare the following magnitude In each case determine 8 g n Give a brief justificati pairs of functions whether f n O g n f n g n f n O g n and or f n in terms of order of on for your answers 1 f n O ln1 oos loglogn 2 f n loglogn 10glogn g n nl 5 logn g n 100n logn 5 3 f n n6 2n 4 g n 4n Problem 3 1 Show that en o log log log n r for any constant 2 Show that i l ik is 8 nk 1 C Problem 4 Do Problem 7 4 2 p 184 Text Problem 5 Do Problem 4 3 8 p 87 Text Replace n2 in recurrence by n Problem 6 Do Problem 4 3 9 p 88 Text Problem 7 Solve the following asymtotic notations recurrences using the method of iteration You may use 1 T n T n 3 n where T O 1 2 T n 6T n 4 n2 where n 4k and T l 1 Problem 8 Do Problem 4 4 9 p 93 Text Problem 9 Do Problem 6 5 9 p 166 Text