Solve each of the following recurrences by the Recursion Tree method. We have provided a complete explanation for this table at the end of this homework. Please read the text before proceeding with this problem. In order to do this, you will complete the following table and the blanks, for each recurrence relation: where d denotes the depth of the recursion tree and has value: d= Adding the last column, we get: T(n)=d1(22)+i=0(23) This solves to T(n)= 1. T(n)=2T(n/2)+n,T(1)=1 2. T(n)=2T(n1)+1,T(0)=1 3. T(n)=T(n/3)+n,T(1)=1 - The level column starts from level 0 which is the root of the tree, and ends at level d which is where the leaf nodes can be found. - Size of Problem: This begins with n in Blank (1) typically. Every level after is influenced by the term inside the recurrence call. - For recurrence relations of the form: T(n)=aT(n/b)+f(n), this goes as n in blank 1 , then blank 5 will have bn, blank 9 will have bin - For recurrence relations of the form: T(n)=aT(nb)+f(n), this goes as n in blank 1 , then blank 5 will have nb, blank 9 will have nib - Depth d : To compute the depth d, you will have to use the base case and the size of the problem at level d, to compute d. - For recurrence relations of the form: T(n)=aT(n/b)+f(n), we know that at level d, the size of the problem is bdn. If we have base case as T(1), then we find d such that bdn=1 or d=logbn. If the base case was some T(x) then we have to find d such that bdn=x or d=x1logbn. - For recurrence relations of the form: T(n)=aT(nb)+f(n), we know that at level d, the size of the problem is nbd. If we have base case as T(0), then we find d such that nbd=0 or d=n/b. If the base case was some T(x) then we have to find d such that nbd=x or d=(nx)/b. - Non-Recursive Cost of One Problem: This is obtained by merely substituting the size of problem in function f(n). - For recurrence relations of the form: T(n)=aT(n/b)+f(n), this goes as f(n) in blank 2, then blank 6 will have f(bn), blank 14 will have f(bin) - For recurrence relations of the form: T(n)=aT(nb)+f(n), this goes as f(n) in blank 2 , then blank 6 will have f(nb), blank 14 will have f(nib) - No. of Problems: This corresponds to the number of nodes in each level of the tree, starting from 1 typically. - For recurrence relations of the form: T(n)=aT(n/b)+f(n), this goes as 1 in blank 3 , then blank 7 will have a, blank 11 will have ai - For recurrence relations of the form: T(n)=aT(nb)+f(n), this goes as 1 in blank 3, then blank 7 will have a, blank 11 will have ai - Total Cost: Simply multiply third and fourth column for every row. So, blank 4 will be product of blanks 2 and 3, and so on. - Blanks 22 and 20 are the same, and Blank 23 is obtained by summing up the last column. - To get 24 , you may use standard simplifications for summations: i=0n1ri=1r1rnifr=1-i=1n1/i=O(logn)-i=1ni=O(n2)i=1ni2=O(n3) Solve each of the following recurrences by the Recursion Tree method. We have provided a complete explanation for this table at the end of this homework. Please read the text before proceeding with this problem. In order to do this, you will complete the following table and the blanks, for each recurrence relation: where d denotes the depth of the recursion tree and has value: d= Adding the last column, we get: T(n)=d1(22)+i=0(23) This solves to T(n)= 1. T(n)=2T(n/2)+n,T(1)=1 2. T(n)=2T(n1)+1,T(0)=1 3. T(n)=T(n/3)+n,T(1)=1 - The level column starts from level 0 which is the root of the tree, and ends at level d which is where the leaf nodes can be found. - Size of Problem: This begins with n in Blank (1) typically. Every level after is influenced by the term inside the recurrence call. - For recurrence relations of the form: T(n)=aT(n/b)+f(n), this goes as n in blank 1 , then blank 5 will have bn, blank 9 will have bin - For recurrence relations of the form: T(n)=aT(nb)+f(n), this goes as n in blank 1 , then blank 5 will have nb, blank 9 will have nib - Depth d : To compute the depth d, you will have to use the base case and the size of the problem at level d, to compute d. - For recurrence relations of the form: T(n)=aT(n/b)+f(n), we know that at level d, the size of the problem is bdn. If we have base case as T(1), then we find d such that bdn=1 or d=logbn. If the base case was some T(x) then we have to find d such that bdn=x or d=x1logbn. - For recurrence relations of the form: T(n)=aT(nb)+f(n), we know that at level d, the size of the problem is nbd. If we have base case as T(0), then we find d such that nbd=0 or d=n/b. If the base case was some T(x) then we have to find d such that nbd=x or d=(nx)/b. - Non-Recursive Cost of One Problem: This is obtained by merely substituting the size of problem in function f(n). - For recurrence relations of the form: T(n)=aT(n/b)+f(n), this goes as f(n) in blank 2, then blank 6 will have f(bn), blank 14 will have f(bin) - For recurrence relations of the form: T(n)=aT(nb)+f(n), this goes as f(n) in blank 2 , then blank 6 will have f(nb), blank 14 will have f(nib) - No. of Problems: This corresponds to the number of nodes in each level of the tree, starting from 1 typically. - For recurrence relations of the form: T(n)=aT(n/b)+f(n), this goes as 1 in blank 3 , then blank 7 will have a, blank 11 will have ai - For recurrence relations of the form: T(n)=aT(nb)+f(n), this goes as 1 in blank 3, then blank 7 will have a, blank 11 will have ai - Total Cost: Simply multiply third and fourth column for every row. So, blank 4 will be product of blanks 2 and 3, and so on. - Blanks 22 and 20 are the same, and Blank 23 is obtained by summing up the last column. - To get 24 , you may use standard simplifications for summations: i=0n1ri=1r1rnifr=1-i=1n1/i=O(logn)-i=1ni=O(n2)i=1ni2=O(n3)