Please show all work, and i do rate, so please get the questions correct.
Instructions (A2 Written) Complete the following problems, when computing Big-O/Big-Q values, they should be as tight as possible. This meansgiving 0(2) as the solution to every problem will not receive credit (although technically true, it would be meaningless). Consider the function f(n)-3n3-39nz + 360n + 20in order to prove that f(n) is (n3), we need constants c, no > 0 such that f(n)2 cm" for every n part. Work should include any steps you performed to solve the problem (e.g., derivations, arithmetic, "I entered this 1. no. Show your work for each into wolfram Alpha" ). (3 points each for 12 total) a. Suppose we fix c2.25. What is the smallest integer value of n that works? b. Suppose we fix c-3. Now what is the smallest integer value of no to satisfy the inequality? c. Suppose we want to fix no 1. Provide some value of c that satisfies the inequality d. Provide a value of c such that no matter what value no takes, the inequality cannot be satisfied. 2. First obtain the source files for the functions binary search rec and binary search rec4. Then read over the code and see how the iterative code for binary search was morphed into the code for binary search rec. In order to reduce the number of recursive calls, consider the code for the function binary_search rec4 that splits the range of the search to 4 parts and then performs the search within one of the 4 quadrants. Does this actually improve performance? In the files you can run tests to compare the runtimes on large inputs. (3 points each for 15 total) Consider the following array of type int named data for the following questions. int data[16] (-3, e, 2, 5, 8, 17, 23, 30, 41, 48, 62, 63, 70, 75, 81, .You may assume data starts at address 0x4000 . When drawing the call stacks, write values of memory addresses the pointers store. Do not draw arrows. Your call stack should have the values stored at the time the final return is called (not necessarily the values the function was called withot the values the loop initializes at/etc) a. Draw the call stack up to the largest point (i.e., just before mid or nullptr is returned) for the function call binary_search_rec(data, data+16, 17) for the function call binary_search_rec4(data, data+16, 17); for the function call binary_search_rec(data+4, data+12, 5); b. Draw the call stack up to the largest point (i.e., just before mid or nullptr is returned) c. Draw the call stack up to the largest point (i.e., just before mid or nullptr is returned)
