Question

Discrete Math

Give a big-Theta estimate for the number of additions in the following algorithm a) procedure f (n: integer) bar = 0; for i = 1 to n^3 for j = 1 to n^2 bar = bar + i + j return bar b) Consider the procedure T given below. procedure T (n: positive integer) if n = 1 return 2 for i = 1 to n^3 x = x + x + x return T(/4) + T(/4) + T(/4) Let f(n) be the number of additions in the procedure for an input of n and note that f(n) satisfies a recurrence relation of the form f(n) = a f(n/b) + cn^4. i) Determine the values of a, b, c, and d. a = b = c = d = ii) Apply The Master Theorem (given below) to T to determine its complexity. Master Theorem Given f(n) = a f(n/b) + cn^4, then f(n) is {theta (n^4) if a < b^4 theta (n^4 log n) if a = b^4 theta (n^log) if a > b^4

Answer 1

a.) Since both loops are running independently from each other, therefore time complexity of nested loop can be given as the product of time complexity associated with each for loop. i.e,

t(n) = theta(n^3 * n^2) = theta(n^5)

b.) Recurrence relation is given as:

t(n) = 3t(n/4) + n^3

i.) which gives

a = 3, b = 4, c = 1 and d = 3

ii.) since, a < b^d, therefore

t(n) = theta(n^d) = theta (n^3)

Hope it helps, feel free to comment in case of any query.