Assignment 1 CSC 581: Analysis of Algorithms Instructions: All answers should be accompanied with clear explanation and mathematical reasonings, whenever applicable. Problem 1: Asymptotic Growth Select 10 out of the following 15 functions and sort them in increasing order of asymptotic growth (big.o growth). 5n 4 logn 4loglogn ns n/a (logn)* (logn) slog nlogre 5 $34 551 n" Problem 2: Solving Recurrences Give asymptotic upper and lower bounds for Tin) for five out of the following recurrences. Assume that T(n) is constant for ns2. Make your bounds as tight as possible and justify your answers. T(n) = 47(1/4) +5n T(n) = 4T("/s) + 5n T(n) = 5T("/4) + 4n T(n) = 25T(1/5) + na T(n) = 47(m/s) + logn T(n) = 47(1/5) + (logn)Svn T(n) = 4T(vn) + (logn) T(n) = 4T(vn) + (logn)2 T(n) = T(vn) + 5 T(n) = T("/2) +27("/s) +T(1/10) + 4n Assignment 1 CSC 581: Analysis of Algorithms Instructions: All answers should be accompanied with clear explanation and mathematical reasonings, whenever applicable. Problem 1: Asymptotic Growth Select 10 out of the following 15 functions and sort them in increasing order of asymptotic growth (big.o growth). 5n 4 logn 4loglogn ns n/a (logn)* (logn) slog nlogre 5 $34 551 n" Problem 2: Solving Recurrences Give asymptotic upper and lower bounds for Tin) for five out of the following recurrences. Assume that T(n) is constant for ns2. Make your bounds as tight as possible and justify your answers. T(n) = 47(1/4) +5n T(n) = 4T("/s) + 5n T(n) = 5T("/4) + 4n T(n) = 25T(1/5) + na T(n) = 47(m/s) + logn T(n) = 47(1/5) + (logn)Svn T(n) = 4T(vn) + (logn) T(n) = 4T(vn) + (logn)2 T(n) = T(vn) + 5 T(n) = T("/2) +27("/s) +T(1/10) + 4n