The analysis of recursive algorithms gives rise to recurrence relations. For Merge Sort, when n is a power of 2 , the recurrence relation is: T(n)=1T(n)=2T(n/2)+nifn=1ifn>1 Using the recursion tree for merge sort, we were able to solve this recurrence relation into its closed form solution: nlogn+n Prove by induction that T(n)=nlogn+n and hence is O(nlogn)