Consider the procedure T given below. procedure T(n: positive integer) for i = 1

Question

Consider the procedure T given below. procedure T(n: positive integer) for i = 1 to n for j = 1 to n x = x + g(x)//Assume that g can be computed in constant time return T(n/2) + T(n/2) + T(n/2) 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^d. a) Determine the values of a, b, c, and d. b) Apply The Master Theorem (given below) to T to determine its complexity. Master Theorem Given f(n) = a f (n/b) + cn^d, then f(n) id {theta(n^d) if a b^d

Explanation / Answer

If we compute the recurrance of the code , we can see it has three subproblems of Size n/2 .

Let T(N) be the total time taken to complete the program,

and there are two for loops , The outer for loop takes n time, the innter one takes nxn = n2 time and the line below also takes n2 time , So total time = 2n2 + n

So, Overall T(N) = 3T(N/2) + 2n2

a = 3 , b = 2, c = 2 , d = 2

Solving using masters theorem :: a = 3 , b = 2

22  = 4 > 3 , So T(N) = Theta(N2)

Thanks, let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.