Draw the recursion tree for T(n) = 2T(Ln/3) + cn, where c is a constant, and...

  

Transcribed Image Text:

Draw the recursion tree for T(n) = 2T(Ln/3) + cn, where c is a constant, and provide a tight asymptotic bound on its solution. Verify your bound using the substitution method (Note: substitution method uses mathematical induction, and is different from recursion tree/iteration method). Note: You first need to briefly explain your ideas to solve the problem, e.g. what data structures are used, how the intermediate results are saved, which sorting strategy is used, and why the final results are correct; Your pseudo code needs to follow the format given in the textbook (e.g. Partition procedure): PARTITION(A,p.r) 1 x = A[r] 2 i-p-1 3 for ptor-1 $ 4 if AU] x 1=1+1 // the pivot // highest index into the low side // process each element other than the pivot // does this element belong on the low side? // index of a new slot in the low side exchange Ali] with Al] // put this element there 7 exchange Ali+1] with A[r] // pivot goes just to the right of the low side 8 return i + 1 // new index of the pivot You can also use any procedures/functions defined in the textbook in your pseudo code. Concrete code from a specific programming language such as Python or Java copied from elsewhere is NOT acceptable. You always need to provide a complexity analysis for your algorithmic design or description. Draw the recursion tree for T(n) = 2T(Ln/3) + cn, where c is a constant, and provide a tight asymptotic bound on its solution. Verify your bound using the substitution method (Note: substitution method uses mathematical induction, and is different from recursion tree/iteration method). Note: You first need to briefly explain your ideas to solve the problem, e.g. what data structures are used, how the intermediate results are saved, which sorting strategy is used, and why the final results are correct; Your pseudo code needs to follow the format given in the textbook (e.g. Partition procedure): PARTITION(A,p.r) 1 x = A[r] 2 i-p-1 3 for ptor-1 $ 4 if AU] x 1=1+1 // the pivot // highest index into the low side // process each element other than the pivot // does this element belong on the low side? // index of a new slot in the low side exchange Ali] with Al] // put this element there 7 exchange Ali+1] with A[r] // pivot goes just to the right of the low side 8 return i + 1 // new index of the pivot You can also use any procedures/functions defined in the textbook in your pseudo code. Concrete code from a specific programming language such as Python or Java copied from elsewhere is NOT acceptable. You always need to provide a complexity analysis for your algorithmic design or description.