2. Consider this recurrence: T(n) Solution: = 4T(n/3)+2n when n > 1, when n = 1....

 

Transcribed Image Text:

2. Consider this recurrence: T(n) Solution: = 4T(n/3)+2n when n > 1, when n = 1. (a) How many levels will the recurrence tree have? (b) What is the cost at the level below the root? (c) What is the cost at the l'th level below the root? (d) Is the cost constant for each level? (e) Find the total cost for all levels. Hint: You may need to use a summation. The Geometric Sum formula may be helpful. (f) If T(n) is (g(n)), find g(n). 2. Consider this recurrence: T(n) Solution: = 4T(n/3)+2n when n > 1, when n = 1. (a) How many levels will the recurrence tree have? (b) What is the cost at the level below the root? (c) What is the cost at the l'th level below the root? (d) Is the cost constant for each level? (e) Find the total cost for all levels. Hint: You may need to use a summation. The Geometric Sum formula may be helpful. (f) If T(n) is (g(n)), find g(n).

Answer rating: 100% (QA)

a size of sub problem at level i if level k is the last level where size of su... View the full answer