Give a big-Theta estimate for the number of additions in the following algorithm

Question

Give a big-Theta estimate for the number of additions in the following algorithm. a) procedure foo (n: integer) bar=0; for i = 1 to n 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 for j = 1 to n x = x + g(x) + x//Assume that can be computed without any additions return T(%) + T(%) + T(%) 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) = af(n/b) + cn^d. 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) = af(n/b)+cn^d, then f(n) is {theta(n^d if a b^d

Explanation / Answer

Ans-

T (n) = 3T (n/2) + n 2 = T (n) = (n 2 ) (Case 3) 2. T (n) = 4T (n/2) + n 2 = T (n) = (n 2 log n) (Case 2) 3. T (n) = T (n/2) + 2n = (2n ) (Case 3) 4. T (n) = 2nT (n/2) + n n = Does not apply (a is not constant) 5. T (n) = 16T (n/4) + n = T (n) = (n 2 ) (Case 1) 6. T (n) = 2T (n/2) + n log n = T (n) = n log2 n (Case 2) 7. T (n) = 2T (n/2) + n/ log n = Does not apply (non-polynomial difference between f(n) and n logb a ) 8. T (n) = 2T (n/4) + n 0.51 = T (n) = (n 0.51) (Case 3) 9. T (n) = 0.5T (n/2) + 1/n = Does not apply (a < 1) 10. T (n) = 16T (n/4) + n! = T (n) = (n!) (Case 3) 11. T (n) = 2T (n/2) + log n = T (n) = ( n) (Case 1) 12. T (n) = 3T (n/2) + n = T (n) = (n lg 3 ) (Case 1) 13. T (n) = 3T (n/3) + n = T (n) = (n) (Case 1) 14. T (n) = 4T (n/2) + cn = T (n) = (n 2 ) (Case 1) 15. T (n) = 3T (n/4) + n log n = T (n) = (n log n) (Case 3) 16. T (n) = 3T (n/3) + n/2 = T (n) = (n log n) (Case 2) 17. T (n) = 6T (n/3) + n 2 log n = T (n) = (n 2 log n) (Case 3) 18. T (n) = 4T (n/2) + n/ log n = T (n) = (n 2 ) (Case 1) 19. T (n) = 64T (n/8) n 2 log n = Does not apply (f(n) is not positive) 20. T (n) = 7T (n/3) + n 2 = T (n) = (n 2 ) (Case 3) 21. T (n) = 4T (n/2) + log n = T (n) = (n 2 ) (Case 1) 22. T (n) = T (n/2) + n(2 cos n) = Does not apply. We are in Case 3, but the regularity condition is violated. (Consider n = 2k, where k is odd and arbitrarily large. For any such choice of n, you can show that c 3/2, thereby violating the regularity condition.)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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