Please help answer all. Thanks

Safari File Edit View History Bookmarks Window Help 99% H. Sun 4:10 PM QE Wayne State University 0 Welcome, Leng -Blackboard Learn https:/blackboard.wayne.edu/bbcsweb... Facebook Fwd: logicly key - lengl96@ Safari File Edit View History Bookmar. Questions (100 points) 1, (15 points) Prove the following assertions by using the definitions ore, o and , or disprove them by giving a specific counterexample. (a) 3n2 -5n +4 E O(n3) (b) log2 ne (Inn) 2. (15 points) Find the order of growth of the following sums. (a) 2 (b) (2n+ n), -0 3. (15 points) Order the following functions according to their order of growth (from the lowest to the highest) 4. (15 points) Solve the following recurrence relation x(n) = x(n-1) + n for n > 0, r(0) = 0 5. (15 points) Consider the following algorithm Algorithm 1 Algorithm S(n) 1: //Input: A positive integer rn 2: //Output: The sum of the first n cubes 3: if n= 1 then 4: return 1 5: else 6: retrn [S(n - 1)+n*n*n (a) Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed. (b) How does this algorithm compare with the straightforward nonrecursive algorithm for computing this function