Consider the following recurrence relation: T(n): = {3T (n/3) + m if n = 1 37(n/3)+n...

Transcribed Image Text:

Consider the following recurrence relation: T(n): = {3T (n/3) + m if n = 1 37(n/3)+n if n>1 (25 points). Carefully draw the recurrence tree for this relation to a depth of three. (Remember that the root lies at depth zero.) At each level of the tree, the branches are identical; there is no need to show the same information for branches on the same level. Your answer should clearly show (1) the per-node cost at each level, (2) the number of nodes at each level, (3) the total cost at each level, (4) the depth of the tree, and (5) the number of leaf nodes and their associated cost. (15 points). Make an educated guess for some upper bound on the recur- rence relation. Prove your guess is correct using an inductive, substitution- based proof. Carefully show all of your steps, making it clear what you are assuming, and what you are trying to prove. Consider the following recurrence relation: T(n): = {3T (n/3) + m if n = 1 37(n/3)+n if n>1 (25 points). Carefully draw the recurrence tree for this relation to a depth of three. (Remember that the root lies at depth zero.) At each level of the tree, the branches are identical; there is no need to show the same information for branches on the same level. Your answer should clearly show (1) the per-node cost at each level, (2) the number of nodes at each level, (3) the total cost at each level, (4) the depth of the tree, and (5) the number of leaf nodes and their associated cost. (15 points). Make an educated guess for some upper bound on the recur- rence relation. Prove your guess is correct using an inductive, substitution- based proof. Carefully show all of your steps, making it clear what you are assuming, and what you are trying to prove.