3. This question refers to the following code. Assume that the / symbol represents integer division: a/b = []. 1 2 3 4 5

[answerhappygod]

3 This Question Refers To The Following Code Assume That The Symbol Represents Integer Division A B 1 2 3 4 5 1 (125.49 KiB) Viewed 58 times

3 This Question Refers To The Following Code Assume That The Symbol Represents Integer Division A B 1 2 3 4 5 2 (84.94 KiB) Viewed 58 times

3. This question refers to the following code. Assume that the / symbol represents integer division: a/b = []. 1 2 3 4 5 6 // pre: (A.length >= 1) ^ (0 <= j, k < A.length) void myFnc (int[] A, int j, int k) if (j < k-1) doStuff (A, j, k) myFnc (A, j, (2*j+k)/3) myFnc (A, (j+2*k)/3 + 1, k) Let n = kj+1. Assume that doStuff (A, j, k) performs some operation on the entries A[j], A [K] inclusive, and that if this function acts on n = k-j+1 entries, its cost is n². (a) [3 marks] Let T(n) be the cost of myFnc() as a function of the input size n. Find the recurrence relation that defines T(n). (Caution: what values of n are base cases?) Use the simplified conventions for counting steps that were described and used in the Week 6 notes. For example, a fixed number of steps that does not depend on the size of n can be approximated by 1. For any function f(n) such that f(n) = w(1), the sum f(n) + 1 can be approximated by f(n). You will need to use the floor and/or ceiling functions. The only variable should be n: the indices j and k should not appear. Once you have eliminated j and k in favor of n, you do not need to simplify your expression in any particular way. However, if you choose to simplify, it might be useful to recall that for any x ER, -[x] = [-x], - [x] = [-x] For parts (b), (c) and (d), assume that n = 3" for some integer r ≥ 0.
For parts (b), (c) and (d), assume that n = 3" for some integer r≥ 0. (b) [2 marks] In the special case where n = 3" for some integer r ≥ 0, show that your recurrence relation from part (a) can be simplified to the following form. T(n) = = { n ≤ c d, aT (1) + f(n), n>c 2 (c) [4 marks] Draw the recursion tree for your recurrence relation from part (b). Include enough rows to establish a pattern for the entries. Calculate the sum of each row, and find a lower bound and an upper bound for the sum of all of the entries in the tree. Use that result to conjecture a function g(n) so that T(n) = (g(n)). It might be useful to recall the sum of an infinite geometric series: for any q such that 0 <q < 1, Σqk= k=0 1 1 q (d) [2 marks] Explain which case of the Master Theorem applies to the recurrence relation from part (b), and use that case to prove your conjecture from part (c).