a. Draw a recursion tree for the recurrence T(n) = T(an) + ((1-a)n) + cn, where...

Transcribed Image Text:

a. Draw a recursion tree for the recurrence T(n) = T(an) + ((1-a)n) + cn², where 0 < a < 1 and c> 0 are constants. Draw the nodes at three depths, i.e., level 0, 1, and 2 (root node is depth 0). Show the cost of each level. b. Assume that the procedure FUN(n) has a running time of 0 (n), and we have designed an algorithm as follows: SOME-ALGO(n) 1. i=1 2. while i<n 3. 4. FUN(n) i=i+2 How many times is FUN( executed for best and worst case scenarios? (Assuming that is an exact power of 2) Answer with reason. Determine the running time of SOME-ALGO(n) for the worst case scenario. Show your work to get full points. a. Draw a recursion tree for the recurrence T(n) = T(an) + ((1-a)n) + cn², where 0 < a < 1 and c> 0 are constants. Draw the nodes at three depths, i.e., level 0, 1, and 2 (root node is depth 0). Show the cost of each level. b. Assume that the procedure FUN(n) has a running time of 0 (n), and we have designed an algorithm as follows: SOME-ALGO(n) 1. i=1 2. while i<n 3. 4. FUN(n) i=i+2 How many times is FUN( executed for best and worst case scenarios? (Assuming that is an exact power of 2) Answer with reason. Determine the running time of SOME-ALGO(n) for the worst case scenario. Show your work to get full points.