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 44 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.