First NameLast NameQuiz #03CSC 172 (Data Structures & Algorithms)Spring 2019Feb 10 - 16Time: 15 minutesProblem 1 (3 pts)Assume each of the following expressions below gives the running timeT (n) of an algorithm for solving a problem of size n. Select the domi-nant terms having the steepest (’fastest’) increase in n and specify thelowest Big-Oh complexity of each algorithm.Expression Dominant term(s) O(. . .)1. 0.3n + 5n1.5+ 2.5 · n1.752.5 · n1.75O(n1.75)2. n2log2n+n(log2n)2n2log2n O(n2log n)3. nlog3n+nlog2n n log3n, n log2n O(n log n)Problem 2 (2 pts)What is the value returned by the method leonardo() defined as:public int leonardo(int n) {if(n == 0)return 0;else if(n == 1)return 1;elsereturn leonardo(n - 1) + leonardo(n - 2);}if called with 4 as an argument, so if you call it as leonardo(4).Answer: 3Page 1 of 2Problem 3 (3 pts)Order the following functions in increasing order of asymptotic growthrates. No explanation required.n2/(log n)2, n√n, n23n, n2(log n)2, (log n)3n3.2Solution:n√n << n2/(log n)2<< n2(log n)2<< (log n)3n3.2<< n23nProblem 4 (2 pts)Draw the recursion tree for the following recurrence relation:T (n) = 3T (n/4) + cn2Note: You don’t need to construct a complete tree, but only 3 levelsof the tree.Page 2 of
View Full Document