Draw the complete recursion tree for merge sort analysis for n=2⁴ (similar to the tree in Slide 23 of Lecture 2). Draw the complete tree up to the last level. Then calculate the number of steps for merging at each level. Finally, find the total number of steps for merging by numbers (not in O notation). Everything should be done for n = 2⁴ (not for n = 2^m).

Q4. Solve the following recurrence by iterative method. Assume n as an even integer.

s(n)=0n=0n+s(n-2)n>0

Q5. Solve the following recurrence by Master method.

T(n)=25T(n/5)+2n