CSC 421 Test ANSWER ALL Questions 1. Solve the following recurrences exactly or asymptotically (big Oh) (25 %) 0 (a) T(n)-T(n 1)+n; T(0)= 2 Use the substitution method to show that T(n-T(n-1) + (n) has the solution 7(n) Show that T(n)-O(n2), show that T(n) 0(n2), then combine the two results to sho (25% ; 9(nz) (F w that T(n)-0() INT 3.Given :ra urray of n integers. i 25% ta) Give tise best algorithm for searcling for an eiement X if the array is sorted, and analyze its asymptotic Wonsts-case running tirne. the besi algorithm for searching for X if the array is not sorted and analyze its asymptotic worst-case ey Give the best algorithm for finding the maximum element MAX in the array if the array is not sorted and rinning time. anelyze it worst-case running time 4 Prove symptotic tight bound (0) for the following functions (25%) (b)T(n) 2n3., 4n + 4 ; (c ) T(n) -2n +4n+4, Prove T(n) = (m) Prove T(n)2)