Problem 1 (2 points) Solving Recurrence Relations Draw the recursion tree for () = 2(/3) + , 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) 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